圖的程度序列和狀態

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：157

、訪客IP：18.191.84.32

姓名

才維翰(Wei-han Tsai) 查詢紙本館藏

畢業系所

數學系

論文名稱

圖的程度序列和狀態
(Degree Sequences and Statuses in Graphs)

相關論文

★ 圖之均勻分解與有向圖之因子分解	★ 加權圖之和、中位點及位移
★ 迴圈之冪圖的星林分解數	★ 圖形的線性蔭度及星形蔭度
★ On n-good graphs	★ A Note On Degree-Continuous Graphs
★ Status Sequences and Branch-Weight Sequences of Trees	★ 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 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

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

摘要(中)

在我的博士論文裡面我考慮了一些有關 degree sequences 和 statuses問題。
在第二章裡面我在一些特殊的 families 找出哪些圖在那些我所指定的 family 是唯一的, 例如: trees, connected regular graphs, forests, unicyclic graphs 和 bicyclic graphs。
在第三章裡面我考慮的問題是如何將一個圖嵌入另一個圖之中﹐並且使的原本的圖是後來這個擴展的圖的median。
在第四章裡面我先介紹了一個圖的變化光譜的定義。並且找出某幾類的圖的變化光譜。另外﹐在點數跟maximum degree固定的情況下﹐我也找出了到底有哪些圖的 status 可以達到最小。

摘要(英)

In this thesis, we consider some problems about degree sequences and statuses
of graphs.
In Chapter 2 we obtain the graphs which are degree unique in trees, connected
regular graphs, forests, unicyclic graphs and bicyclic graphs, respectively.
In Chapter 3 we consider the problem of embedding a given graph as the
median of another graph. We investigate the problem in the weighted version
and for some related notions such as antimedian and i-th median (i = 1, 2, . . .).
In Chapter 4 we investigate the variance spectrums of graphs. We also
characterize the graphs whose minimum statuses attain the minimum in the
family of graphs with fixed maximum degree and order

關鍵字(中)

★ 程度序列
★ 狀態

關鍵字(英)

★ degree sequence
★ status

論文目次

Contents
1 Introduction 1
1.1 Basic Definitions and Notations . . . . . . . . . . . . . . . . . . 1
1.2 Overview of the Thesis . . . . . . . . . . . . . . . . . . . . . . . 3
2 Degree Unique Graphs 5
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.2 Degree Unique Graphs in Trees . . . . . . . . . . . . . . . . . . 7
2.3 Degree Unique Graphs in Unicyclic Graphs and Bicyclic Graphs 12
3 Embedding Results for Medians and Antimedians 23
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.2 Embedding Results for Medians . . . . . . . . . . . . . . . . . . 25
3.3 Embedding Results for Medians and Antimedians . . . . . . . . 33
4 Minimum Statuses and Variance Spectrums 51
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
4.2 Minimum Statuses . . . . . . . . . . . . . . . . . . . . . . . . . 55
4.3 Variance Spectrums . . . . . . . . . . . . . . . . . . . . . . . . . 65
References 69

參考文獻

[1] W. Aitken, Total relative displacements of permutation, Journal of Combinatorial
Theory Ser. A 87, 1-21 (1999)
[2] K. Balakrishnan, B. Breˇsar, M. Changat, S. KlavˇZar, M. Kovˇse, A.R. Subhamathi,
Simultaneous embeddings of graphs as median and antimedian
subgraphs. Networks 56 (2010), no. 2, 90-94
[3] L.W. Beineke, O.R. Oellermann, and R.E. Pippert, On the Steiner median
of a tree, Discrete Applied Mathematics. 68, no. 3, 249-258 (1996)
[4] C.-F. Chang, H.-L. Fu, Near automorphisms of trees with small total
relative displacements, Journal of Combinatorial Optimization 14, 191-
195 (2007)
[5] R.C. Entring, D.E. Jackson and D.E. Snyder, Distance in graphs, Czech.
Math. J. 26, 283-296 (1976)
[6] A.J. Goldman, Minimax location of a facility in a network, Transportation
Science 6, 407-418 (1972)
[7] S.L. Hakimi, Optimum locations of switching centers and medians of a
graph, Operations Resarch 12, 450-459 (1964)
[8] R.H. Johnson, The diameter and radius of simple graphs, Journal of Combinatorial
Theory Ser.B 17, 188-198 (1974)
69
[9] R.H. Johnson, Simple separable graphs, Pacific Journal of Mathematics
56, no. 1, 143-158 (1975)
[10] R.H. Johnson, A survey of simple graphs. Proceedings of the Ninth Southeastern
Conference on Combinatorics, Graph Theory, and Computing
(Florida Atlantic Univ., Boca Raton, Fla., 1978), 395-400
[11] R.H. Johnson, Properties of unique realizations—a survey, Discrete Mathematics
31, no. 2, 185-192 (1980)
[12] H.-Y. Lee and G. J. Chang, Medians of graphs and kings of tournaments,
Taiwanese J. of Mathematics, Vol. 1, 103-110 (1997)
[13] C. Lin, W.-H. Tsai, Y.-J. Zhang, J.-L. Shang, Minimum statuses of connected
graphs with fixed maximum degree and order. Journal of Combinatorial
Optimization, to appear
[14] Z. Miller, Medians and distance sequence in graphs, Ars Combinatoria,
vol. 15, 169-177 (1983)
[15] O.R. Oellermann, From Steiner centers to Steiner medians, Journal of
Graph Theory. 20, no 2, 113-122 (1995)
[16] O.R. Oellermann, On Steiner centers and Steiner medians of graphs. Centrality
concepts in network location. Networks 34, no. 4, 258-263 (1999)
[17] L. Pacher, Constructing status injective graphs, Discrete Applied Mathematics
80, 107-113 (1997)
[18] K.B. Reid, Total relative displacements of complete t-partite graph, Journal
of Graph Theory 41, 85-100 (2002)
[19] P.J. Slater, Maximin facility location. Journal of Research of the National
Bureau of Standards-B, Mathematical Sciences Vol. 79B, No. 3 and 4,
107-115 (1975)
70
[20] P.J. Slater, Medians of arbitrary graphs, Journal of Graph Theory vol 4,
389-392 (1980)
[21] E.T.H. Wang, The symmetric group as a metric space, E2424, Amer.
Math. Monthly, vol. 81, no. 6, 668-670 (1974)
[22] H.-G. Yeh, C.-Y. Chiang, S.H. Peng , Steiner centers and Steiner medians
of graphs, Discrete Mathematics 308, no. 22, 5298-5307 (2008)

指導教授

林強(Chiang Lin)

審核日期

2012-1-16

推文