博碩士論文 87241005 詳細資訊




以作者查詢圖書館館藏 以作者查詢臺灣博碩士 以作者查詢全國書目 勘誤回報 、線上人數:11 、訪客IP:100.24.122.228
姓名 黃文婷(Wen-Ting Huang)  查詢紙本館藏   畢業系所 數學系
論文名稱 圖形的線性蔭度及星形蔭度
(Linear Arboricity and Star Arboricity of 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 格式]    [相關文章]   [文章引用]   [完整記錄]   [館藏目錄]   [檢視]  [下載]
  1. 本電子論文使用權限為同意立即開放。
  2. 已達開放權限電子全文僅授權使用者為學術研究之目的,進行個人非營利性質之檢索、閱讀、列印。
  3. 請遵守中華民國著作權法之相關規定,切勿任意重製、散佈、改作、轉貼、播送,以免觸法。

摘要(中) 一個線性森林(linear forest)是一個森林(forest),其中每一個部分(component)是一條路徑(path)。令G是一個圖(graph)。G的蔭度(arbori- city),用a(G)來表示,是分解G的邊所需要的最少的森林數。G的線性蔭度(linear arboricity),用la(G)來表示,是分解G的邊所需要的最少的線性森林數。G的不限路徑數(unrestricted path number),是覆蓋G的邊所需要的最少的路徑數。在第二章中,我們得到規則完全r部圖(regular complete r-partite graphs)的線性蔭度及不限路徑數。在第三章中,我們得到完全三部圖(complete tripartite graphs)的線性蔭度。
對一個圖G一個正整數k,令G^k代表V(G)=V(G^k)且E(G^k)={uv:u,v in V(G), u
e u, d_G(u,v)le k}的圖,其中d_G(u,v)代表在G中u和v的距離。我們稱G^k為G的k次方。
一個每個部分(component)都是星形(star)的森林稱為星林(star for- est )。G的星形蔭度(star arboricity),用sa(G)來表示,是分解G的邊所需要的最少的星林數。在第四章中,我們得到迴路(cycle)的次方的星形蔭度。在第五章中我們進一步提出了一些相關的問題。
摘要(英) Let G be a graph. The unrestricted path number of G, denoted by
ho(G), is the minimum number of paths needed to cover the edges of G. The arboricity of G, denoted by a(G), is the minimum number of forests needed to decompose the edges of G. A linear forest is a forest in which each component is a path. The linear arboricity of G, denoted by la(G), is the minimum number of linear forests needed to decompose the edges of G. In Chapter 2, we study the linear arboricity and unrestricted path number of regular complete r-partite graphs. Let K_{r imes n} denote the complete r-partite graph such that each part has n$vertices, For rge 2, we obtain
a(K_{r imes n})= la(K_{r imes n})=
ho (K_{r imes n})=lceil frac{(r-1)n+1}{2}
ceil.
In Chapter 3, we study the linear arboricity of complete tripartite graphs. Suppose n_1ge n_2ge n_3, we obtain
la(K_{n_1, n_2, n_3})=n_1+1 if n_1=n_2=n_3, and
la(K_{n_1, n_2, n_3})=lceilfrac{n_1+n_2}{2}
ceil otherwise.
For a graph G and a positive integer k, let G^k denote the graph with V(G^k)=V(G) and E(G^k)={uv : u, vin V(G), u
e v, d_G(u, v)le k} where d_G(u, v) denotes the distance between u and v in G. We call G^k the k-th power of G.
A star forest is a forest in which each component is a star. The star arboricity of a graph G, denoted by sa(G), is the minimum number of star forests needed to decompose the edges of G. In Chapter 4, we study the star arboricity of power of cycles. Suppose that k, n are integers such that 2le kle lfloorfrac{n}{2}
floor-1, we obtain
sa(C_n^k)=k+1 if n=0(mod k+1), and
sa(C_n^k)=k+2 otherwise
In Chapter 5, some problems are proposed for further investigations.
關鍵字(中) ★ 完全三部圖
★ 迴路的次方
★ 完全多部圖
★ 不限路徑數
★ 星形蔭度
★ 線性蔭度
關鍵字(英) ★ complete tripartite graph
★ complete multipartite graph
★ power of cycle
★ linear arboricity
★ star arboricity
★ unrestricted path number
論文目次 Abstract i
Contents iii
List of Figures v
1 Introduction 1
1.1 Basic definitions in graph theory.......................................1
1.2 Linear arboricity.......................................................4
1.3 Star Arboricity.........................................................6
2 Linear Arboricity and Unrestricted Path Number of Regular Complete r-Partite Graphs 8
2.1 Introduction and preliminaries..........................................8
2.2 Main results...........................................................10
3 Linear Arboricity of Complete Tripartite Graphs 28
3.1 Introduction and preliminaries.........................................28
3.2 Main results...........................................................32
4 Star Arboricity of Power of Cycles 59
4.1 Introduction and preliminaries.........................................59
4.2 Main results...........................................................61
5 Conclusions 78
Bibliography 80
參考文獻 [1] H. Ait-Djafter, Linear arboricity for graphs with maximum degree six or seven and edge multiplicity two, Ars. Combinatoria 20 (1985), 5-16.
[2] J. Akiyama, A status on the linear arboricity, Lecture Notes in Computer Science 108 (1981), 38-44.
[3] J. Akiyama and V. Chvatal, A short proof of the linear arboricity for cubic graphs, Bull. Liber. Arts and Sci., NMS 2 (1981), 1-3.
[4] J. Akiyama, G. Exoo, F. Harary, Covering and packing in graphs III: cyclic and acyclic invariants, Math. Slovaca 30 (1980), 405-417.
[5] J. Akiyama, G. Exoo, F. Harary, Covering and packing in graphs IV: linear arboricity, Networks 11 (1981), 69-72.
[6] J. Akiyama, T. Hamada, The decompositions of line graphs, middle graphs and total graphs of complete graphs into forests, Discrete Math. 26 (1979), 203-208.
[7] J. Akiyama and M. Kano, Path factors of a graph, in Graph Theory and its Applications, Proc. First Colorado Sympo. on Graph Theory (Wiley, New York 1985), 1-21.
[8] I. Algor and N. Alon, The star arboricity of graphs, Discrete Math. 75 (1989), 11-22.
[9] N. Alon, The linear arboricity of graphs, Israel J. Math. 62 (1988), 311-325.
[10] N. Alon, C. McDiarmid and B. Reed, Star arboricity, Combinatorica 12 (1992), 375-380.
[11] Y. Aoki, The star-arboricity of the complete regular multipartite graphs,
Discrete Math. 81 (1990), 115-122.
[12] M. Behzad, G. Chartrand and L. Lesniak-Foster, Graphs and Digraphs, Wadsworth, Belmont, CA, (1979).
[13] J. A. Bondy and U. S. R. Murty, Graph Theory with Applications, North Holland, New York (1976).
[14] J. Bosak, Decompositions of Graphs, Kluwer, Dordrecht, Netherlands, 1990.
[15] G. Chartrand, L. Lesniak, Graphs and Digraphs, 2nd Edition, Wadsworth, Belmont, CA, (1986).
[16] Y. Egawa, M. Urabe, T. Fukuda and S. Nagoya, A decomposition of complete bipartite graphs into edge-disjoint subgraphs with star components,
Discrete Math. 58 (1986), 93-95.
[17] H. Enomoto, The linear arboricity of 5-regular graphs, Technical Report,
Dept. of Information Sci., Univ. of Tokyo, 1981.
[18] H. Enomoto and B. Peroche, The linear arboricity of some regular graphs,
J. Graph Theory 8 (1984), 309-324.
[19] H. Enomoto and Y. Usami, The star arboricity of complete bipartite graphs,
Graph Theory, Combinatorics, and Applications 1 (1988), 389-396.
[20] B. Guiduli, Note on incidence coloring and star arboricity of graphs,
Discrete Math. 163 (1997), 275-278.
[21] F. Guldan, The linear arboricity of 10-regular graphs, Math. Slovaca 36 (1986), 225-228.
[22] F. Guldan, Some results on linear arboricity, J. Graph Theory 10 (1986), 505-509.
[23] M. Habib and B. Peroche, Some problems about linear arboricity, Discrete Math. 41 (1982), 219-220.
[24] S. L. Hakimi, J. Mitchem and E. Schmeichel, Star arboricity of graphs, Discrete Math. 149 (1996), 93-98.
[25] F. Harary, Covering and packing in graphs I, Ann. New York Acad. Sci. 175 (1970), 198-215.
[26] F. Harary and A. J. Schwenk, Evolution of the path number of a graph: Covering and packing in graphs II, Graph Theory and Computing, edited by R. C. Read, Acad. Press, NY, (1972), 39-45.
[27] P. Hell, A. Rosa, Graph decompositions, handcuffed prisoners and balanced P-designs, Discrete Math. 2 (1972), 229-252.
[28] A. Kurek, Arboricity and star arboricity of graphs, Fourth Czechoslovakian Symposium on Combinatorics, Graphs and Complexity (1992), 171-173.
[29] C. Nash-Williams, Decomposition of finite graphs into forests, J. London Math. Soc. 39 (1964), 12.
[30] B. Peroche, The path-numbers of some multipartite graphs, Ann. of Discrete Math. 9 (1980), 195-197.
[31] B. Peroche, On partition of graphs into linear forests and dissections.
[32] R. Stanton, D. Cowan and L. James, Some results on path numbers, Proc. Louisiana Conf. Combinatorics, Graph theory and Computing, Baton Rouge (1970), 112-135.
[33] R. Stanton, L. James and D. Cowan, Tripartite path numbers, Graph Theory and Computing (1972), 285-294.
[34] P. Tomasta, Note on linear arboricity, Math. Slovaca 32 (1982), 239-242.
[35] M. Truszczynski, Decomposing graphs into forests of stars, Congr. Numer. 54 (1986), 73-86.
[36] D. B. West, Introduction to Graph Theory, Prentice-Hall (1996).
[37] T. W. Yeh, Linear Arboricities of Complete r-Partite Graphs, Master Thesis, Dept. Applied Math., National Chiao Tung Univ., Hsinchu, Taiwan, June 1997.
指導教授 林強(Chiang Lin) 審核日期 2003-7-10
推文 facebook   plurk   twitter   funp   google   live   udn   HD   myshare   reddit   netvibes   friend   youpush   delicious   baidu   
網路書籤 Google bookmarks   del.icio.us   hemidemi   myshare   

若有論文相關問題,請聯絡國立中央大學圖書館推廣服務組 TEL:(03)422-7151轉57407,或E-mail聯絡  - 隱私權政策聲明