Status   Sequences   and   Branch-Weight Sequences  of   Trees

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：9

、訪客IP：52.14.221.113

姓名

商珍綾(Jen-Ling Shang) 查詢紙本館藏

畢業系所

數學系

論文名稱

(Status Sequences and Branch-Weight Sequences of Trees)

相關論文

★ 圖之均勻分解與有向圖之因子分解	★ 加權圖之和、中位點及位移
★ 迴圈之冪圖的星林分解數	★ 圖形的線性蔭度及星形蔭度
★ On n-good graphs	★ A Note On Degree-Continuous Graphs
★ n-realizable Quadruple	★ 圖形的路徑分解,迴路分解和星形分解
★ 星林圖的二分解與三分解	★ 2-decomposable, 3-decomposable multipaths and t-decomposable spiders
★ 圖形分解與反魔圖	★ The antimagic graph with a generalization
★ 圖的程度序列和狀態	★ The 3-split of multipaths and multicycles with multiplicity 2
★ 圖形之分割與反魔標號

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

本電子論文使用權限為同意立即開放。
已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。

摘要(中)

關於圖( graph)的研究，圖中資料形成的數列(sequence)，經常提供了明確的數據，讓研究者得以一窺圖所蘊涵的道理。數列提供的是一個圖對於某些性質的整體表現，它往往比單一的數值更有意義，更適合作為思考與猜測的憑藉。因此，根據圖中數列透露出的訊息來研究圖的方法，長久以來廣泛的受到重視與使用。
本篇論文共分為五章，第一章介紹相關的定義及文章。B. Zelinka (1968, [Zel])證明了對於任意一個樹(tree)，它的median與centroid是相同的。A. Kang與D. Ault (1975, [Kang])則證明了若是將樹的邊(edge)加上權重(weight)，此結論亦真。第二章中，2-1節裡，我們獲得了圖中關於status與branch-weight的許多性質，並將上述的結論加以推廣，得到了對任意一個有權重的樹(a weighted tree , 即對所有邊與點(vertex)都賦予權重的樹)，它的median恆與centroid相同。2-2節裡，我們證明了對於任意一個所有邊的權重皆為1的有權重的樹，其second median恆與second centoid相同。
第三章中，我們給予了樹中status數列的一些性質，而其主要結論為，若是一個樹與一個蜘蛛(spider)有相同的status數列，則它們是相同的(they are isomorphic)。
第四章中,在4-1章節裡，我們給予了許多例子，來觀察不同性質的樹之status數列。4-2節得到了一個主要結論，一個樹若與另一個weakly status-injective的樹有相同的status數列，則它們是相同的。
第五章中，在5-1節裡，我們給予了許多不相同的(nonisomorphic trees)卻具有相同的branch-weight數列的例子。5-2節裡，我們介紹了如何由一個蜘蛛所產生的branch-weight數列，重新將這個唯一的蜘蛛構造出來的方法，從而產生了主要的定理，如果有兩個蜘蛛有相同的branch-weight數列，則它們是相同的。

摘要(英)

Abstract
B. Zelinka [Zel] showed that the median of any tree is equal to its centroid. A. Kang and D. Ault [Kang] extended this result for any tree with weights on its edges. In Chapter 2, we extend the result further to any tree with
weights on its edges and vertices and show that the second median of any tree with weights on its vertices is equal to its second centroid. The main result in Chapter 3 is that if S is a spider, T is a tree and S , T have the same status sequence,than S is isomorphic to T . In Chapter 4, we show that if T is a weakly
status-injective tree, T’’ is a tree, and T ,T’’ have thesame status sequence, then T is isomorphic to T’’. The main result in Chapter 5 is that if two spiders have the same branch-weight-sequence, then they are isomorphic.

關鍵字(中)

關鍵字(英)

★ Trees
★ Status
★ Branch-Weight Sequences
★ Sequences

論文目次

Contents
Abstract i
Contents ii
List of Figures iii
1. Introduction and Preliminaries 1
2. Median , Centroid , Second Median and Second Centroid 6
2.1 Medians and centroids in weighted graphs 6
2.2 Second median and second centroid 14
3. Status Sequences of Spiders 19
4. Status Sequences of Weekly Status-Injective Trees 32
4.1 Examples 32
4.2 Main result 38
5. Branch-Weight Sequences of Spiders 51
5.1 Examples 51
5.2 Main result 55
References 59

參考文獻

References
1.
[Buckley] F. Buckley and F. Harary, Distance in Graphs, Addison-Wesley
Publishing company (1990).
2.
[Band] H-J Bandelt and V. Chepo, Graphs with connected medians,
SIAM J. Discrete Math, Vol. 15, 268-282 (2002).
3.
[Ent] R. C. Entringer, Albuquerque, D. E. Jackson, Los Alamos, D. A.
snyder, Distance in graphs, Czech. Math. J. 26, 283-296 (1976).
4.
[Gold] A. J. Goldman, Minimax location of a facility in a network,
Transportation Science 6, 407-418 (1972).
5.
[Hak] S. L. Hakimi, Optimum locations of switching centers and medians
of a graph, Operation Research 12, 450-459 (1964).
6.
[Kang] Andy N. C. Kang and David A. Ault, Some properties of a centroid
of a free tree, Information Processing Lett. 4, No. 1, 18-20 (1975).
7.
[Lee] H-Y Lee and G. J. Chang, The w-median of a connected strongly
chordal graph, J. Graph Theory Vol. 18, No. 7, 673-680 (1994).
8.
[Mit] S. L. Mitchell, Another characterization of the centroid
of a tree, Discrete Math. 24, No. 3, 277-280 (1978).
9.
[Mill] Z. Miller, Medians and distance sequence in graphs, Ars
Combin. 15, 169-177 (1983).
10.
[Piot] W. Piotrowski and M. M. Syslo, A characterization of
centroidal graphs, Combinatorial Optimization, 272-281 (1986).
11.
[Pach] L. Pachter, Constructing status injective graphs, Discrete
Appl. Math. 80, 107-113 (1997).
12.
[Slater1] P. J. Slater, Maximin facility location, J. Mathematical
Sciences, Vol. 79 B, No. 3 and 4 (1975).
13.
[Slater2] P. J. Slater, Medians of arbitrary graphs, J. Graph Theory
Vol. 4, 389-392 (1980).
14.
[Slater3] P. J. Slater, Counterexamples to Randic's conjecture on distance
degree sequences for trees, J. Graph Theory 6, 89-91 (1982).
15.
[Sk1] R. Skurnick, Extending the concept of branch-weight centroid
number to the vertices of all connected graphs via the slater number,
Graph Theory Notes of New York, 33, 28-32 (1997).
16.
[Sk2] R. Skurnick, A characterization of the centroid sequence of a
caterpillar, Graph Theory Notes of New York, 41, 7-13 (2001).
17.
[Zel] B. Zelinka, Medians and peripherians of trees, Arch Math. 4, 87
-95 (1968).

指導教授

林強(Chiang Lin)

審核日期

2005-7-4

推文