  ### 博碩士論文 87241005 詳細資訊

 以作者查詢圖書館館藏 、以作者查詢臺灣博碩士 、以作者查詢全國書目 、勘誤回報 、線上人數：9 、訪客IP：18.210.28.227

(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 ★ 圖形之分割與反魔標號

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

e u, d_G(u,v)le k}的圖，其中d_G(u,v)代表在G中u和v的距離。我們稱G^k為G的k次方。

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 multipartite graph
★ power of cycle
★ linear arboricity
★ star arboricity
★ unrestricted path number

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

 J. Akiyama, A status on the linear arboricity, Lecture Notes in Computer Science 108 (1981), 38-44.
 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.
 J. Akiyama, G. Exoo, F. Harary, Covering and packing in graphs III: cyclic and acyclic invariants, Math. Slovaca 30 (1980), 405-417.
 J. Akiyama, G. Exoo, F. Harary, Covering and packing in graphs IV: linear arboricity, Networks 11 (1981), 69-72.
 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.
 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.
 I. Algor and N. Alon, The star arboricity of graphs, Discrete Math. 75 (1989), 11-22.
 N. Alon, The linear arboricity of graphs, Israel J. Math. 62 (1988), 311-325.
 N. Alon, C. McDiarmid and B. Reed, Star arboricity, Combinatorica 12 (1992), 375-380.
 Y. Aoki, The star-arboricity of the complete regular multipartite graphs,
Discrete Math. 81 (1990), 115-122.
 M. Behzad, G. Chartrand and L. Lesniak-Foster, Graphs and Digraphs, Wadsworth, Belmont, CA, (1979).
 J. A. Bondy and U. S. R. Murty, Graph Theory with Applications, North Holland, New York (1976).
 J. Bosak, Decompositions of Graphs, Kluwer, Dordrecht, Netherlands, 1990.
 G. Chartrand, L. Lesniak, Graphs and Digraphs, 2nd Edition, Wadsworth, Belmont, CA, (1986).
 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.
 H. Enomoto, The linear arboricity of 5-regular graphs, Technical Report,
Dept. of Information Sci., Univ. of Tokyo, 1981.
 H. Enomoto and B. Peroche, The linear arboricity of some regular graphs,
J. Graph Theory 8 (1984), 309-324.
 H. Enomoto and Y. Usami, The star arboricity of complete bipartite graphs,
Graph Theory, Combinatorics, and Applications 1 (1988), 389-396.
 B. Guiduli, Note on incidence coloring and star arboricity of graphs,
Discrete Math. 163 (1997), 275-278.
 F. Guldan, The linear arboricity of 10-regular graphs, Math. Slovaca 36 (1986), 225-228.
 F. Guldan, Some results on linear arboricity, J. Graph Theory 10 (1986), 505-509.
 M. Habib and B. Peroche, Some problems about linear arboricity, Discrete Math. 41 (1982), 219-220.
 S. L. Hakimi, J. Mitchem and E. Schmeichel, Star arboricity of graphs, Discrete Math. 149 (1996), 93-98.
 F. Harary, Covering and packing in graphs I, Ann. New York Acad. Sci. 175 (1970), 198-215.
 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.
 P. Hell, A. Rosa, Graph decompositions, handcuffed prisoners and balanced P-designs, Discrete Math. 2 (1972), 229-252.
 A. Kurek, Arboricity and star arboricity of graphs, Fourth Czechoslovakian Symposium on Combinatorics, Graphs and Complexity (1992), 171-173.
 C. Nash-Williams, Decomposition of finite graphs into forests, J. London Math. Soc. 39 (1964), 12.
 B. Peroche, The path-numbers of some multipartite graphs, Ann. of Discrete Math. 9 (1980), 195-197.
 B. Peroche, On partition of graphs into linear forests and dissections.
 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.
 R. Stanton, L. James and D. Cowan, Tripartite path numbers, Graph Theory and Computing (1972), 285-294.
 P. Tomasta, Note on linear arboricity, Math. Slovaca 32 (1982), 239-242.
 M. Truszczynski, Decomposing graphs into forests of stars, Congr. Numer. 54 (1986), 73-86.
 D. B. West, Introduction to Graph Theory, Prentice-Hall (1996).
 T. W. Yeh, Linear Arboricities of Complete r-Partite Graphs, Master Thesis, Dept. Applied Math., National Chiao Tung Univ., Hsinchu, Taiwan, June 1997.