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

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

(Path, Cycle and Star Decompositions 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. 請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。

(path decomposition)、迴路分解(cycle decomposition)、完全二部

factorization)的問題將被探討。圖形分解與圖形的蔭度(arboricity)

(linear arboricity)與星形蔭度(star arboricity)。

(one-factor)的反向迴路分解的存在給定一個充分必要條件。第五章將

k-arboricity)問題。

mathematical structures are linked to it and its result can be widely applied
in other fields. The factorization is a special type of graph decomposition,
and it has close connections to combinatorial designs. There are various decomposition
problems such as clique decomposition, star decomposition, path
decomposition, cycle decomposition, complete bipartite decomposition, and so
on. Nowadays, they continue to be popular topics of research.
In this thesis, the problems of antidirected cycle decomposition and directed
path decomposition of some digraph, and that of caterpillar factorization of
some graphs are investigated. There are various close connections between
graph decomposition and the arboricity of a graph. In this thesis, we also
show that the linear arboricity and the star arboricity of some graphs.
There are seven chapters in this thesis. In Chapter 1, some basic definitions
and notations are introduced. In Chapter 2, we first establish a necessary and
sufficient condition for the isomorphic path decomposition of complete tripari tite multigraphs. We then investigate the isomorphic directed path decomposition
of complete tripartite multidigraphs.
In Chapter 3, we give a necessary and sufficient condition for the existence
of the antidirected cycle decompositions of complete symmetric graphs. In
Chapter 4, we give a necessary and sufficient condition for the existence of
the antidirected cycle decompositions of complete symmetric graphs minus a
one-factor.
In Chapter 5, the caterpillar factorization of crowns are studied. We first
establish a necessary and sufficient condition for the balanced caterpillar factorization
of crowns. Then we give a necessary and sufficient condition for the
directed caterpillar factorization of symmetric crowns.
In Chapter 6, we first consider the problem of the star arboricity of crowns.
A lower bound is given. Then we investigate the star arboricity of some special
crowns. In Chapter 7, we consider the problem of the linear k-arboricity of
complete graph Kn for some specific k.

1.1 Introduction to decompositions and factorizations of graphs . . 1
1.2 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.3 Overview of the thesis . . . . . . . . . . . . . . . . . . . . . . . 6
2 Path Decompositions of Complete Tripartite Multigraphs 9
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2 Path decompositions of Kn,n,n for odd n . . . . . . . . . . . . 12
2.3 Decomposition of Kn,n,n, n is even . . . . . . . . . . . . . . . . 17
2.4 Directed path decompositions of K n,n,n for odd n . . . . . . . . 21
3 Antidirected cycle decompositions of Complete Symmetric graphs 27
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.2 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.3 Antidirected cycle decompositions of K n . . . . . . . . . . . . . 30
4 Antidirected cycle decompositions of (Kn − I) 45
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
4.2 Antidirected cycle decompositions of (Kn − I) . . . . . . . . . 46
5 Caterpillar Factorization of Crowns and Directed caterpillar
Factorization of Symmetric Crowns 63
5.1 Introduction and preliminaries . . . . . . . . . . . . . . . . . . . 63
5.2 Caterpillar factorization of crown . . . . . . . . . . . . . . . . . 66
5.3 Directed caterpillar factorization of symmetric crowns . . . . . . 68
6 The star arboricity of crowns 73
6.1 Introduction and preliminaries . . . . . . . . . . . . . . . . . . . 73
6.2 Theorems A and B . . . . . . . . . . . . . . . . . . . . . . . . . 76
6.3 Theorem C . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
7 The linear k-arboricity of complete graphs 85
7.1 Introduction and preliminaries . . . . . . . . . . . . . . . . . . . 85
7.2 Lemmas and result . . . . . . . . . . . . . . . . . . . . . . . . . 86
Bibliography.....................97

University of Tokyo, 1980.
[2] J. Akiyama and M. Kano, Path factors of a graph, in: F. Harary and J.
Maybee, eds., Graphs and Aplications: Proc. First Colorado Sympos. on
Graph Theory(Wiley, New York, 1985),1-21.
[3] J. Akiyama, G. Exoo and F. Harary, Covering and packing in graphs III:
cyclic and acyclic invariants, Math. Slovaca 30 (1980),405-417.
[4] I. Algor and N. Alon, The Star Arboricity of Graphs, Discrete Math. 75
(1989), 11-22.
[5] N. Alon, C. McDiarmid and B. Reed, Star arboricity, Combinatorica 12
(1992), 375-380.
[6] B. Alspach and H. Gavlas, Cycle decompositions of Kn and Kn − I, J.
Combin. Theory Ser.B 81 (2001),77-99.
[7] B. Alspach, H. Gavlas, M. ˇ Sajna and H. Verrall, Cycle decompositions.
IV. Complete directed graphs and fixed length directed cycles, J. Combin.
Theory Ser.A 103 (2003),165-208.
[8] Y. Aoki, The star-arboricity of the complete regular multipartite graphs,
Discrete Math. 81 (1990),115-122.
[9] D. Archdeacon, M. Debowsky, J. Dinitz and H. Gavlas, Cycle systems
in the complete bipartite graph minus a one-factor, Discrete Math. 284
(2004),37-43.
[10] L. W. Beineke, Graph decompositions, Congr. Num. 115 (1996),213-226.
[11] J. C. Bermond and D. Sotteau, Graph decompositions and G-designs,
Fifth British Combinatorial Conf., Aberdeen Congr. Num. XV (1975),53-
72.
[12] J. C. Bermond, K. Heinrich and M.-L. Yu, Existence of resolvable path
designs, Europ. J. Combinatorics 11 (1990),205-211.
[13] J. C. Bermond, Cycles dans les graphes et G-configurations, Thesis, University
of Paris XI (Orsay), Paris (1975).
[14] J. A. Bondy, Basic Graph Theory: Paths and Circuits, in Handbook of
Combinatorics, Vol.1, Amsterdam, Elsevier, 1995.
[15] J. Bos´ak, Decompositions of Graphs, Kluwer, Dordrecht, Netherlands,
(1990).
[16] D. De Caen and D. G. Hoffman, Impossibility of decomposing the complete
graph on n points into n − 1 isomorphic complete bipartite graphs,
SIAM J. Discrete. Math. 2 (1989),48-50.
[17] N. J. Cavenagh, Decompositions of complete tripartite graphs into kcycles,
Australas. J. Combin. 18 (1998)193-200.
[18] N. J. Cavenagh and E. J. Billington, Decompositions of complete multipartite
graphs into cycles of even length, Graphs. Combin. 16 (2000)49-65.
[19] G. J. Chang, B. L. Chen, H. L. Fu, K. C. Huang, Linear k-arboricities on
trees, Discrete Appl. Math. 103 (2000),281-287.
[20] B. L. Chen, K. C. Huang, On the linear k-arboricity of Kn and Kn,n,
Discrete Math. 254 (2002),51-61.
[21] L. Chiang, J.-J. Lin, Cycle decompositions of Crowns, Discrete Math. 220
(2000),251-255.
[22] F. R. K. Chung, G. L. Graham, Recent advances in graph decomposition,
in: H. N. V. Temperley(Ed.), Proceeding of the Eighth British Combinatorial
Conference(University College, Swansea, 1981) London Mathematic
Society Lecture Notes 52, Cambridge University Press, Cambridge,
(1981), 103-124.
[23] M. Debowsky, Results on planar hypergraphs and on cycle decompositions,
Master’s Thesis, University of Vermont (2002).
[24] B. Du, K1,p2 -factorization of complete bipartite graphs, discrete Math.
187 (1998),273-279.
[25] 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.
[26] N. Enomoto, T. Miyamoto and K. Ushio, Ck-factorization of complete
bipartite graphs, Graph Comb. 4 (1988),111-113.
[27] O. Favaron and M. Kouider, Path partitions and cycle partitions of Eulerian
graphs of maximum degree 4, Stud. Sci. Math. Hung. 23 (1988),237-
244.
[28] H. Fleischner, Eulerian graphs and related topics, Part 1,Vol. 1,Ann. Discrete
Math. 45 Amsterdam, North-Holland (1990).
[29] H. Fleischner, Eulerian graphs and related topics, Part 1,Vol. 2,Ann. Discrete
Math. 50 Amsterdam, North-Holland (1991).
[30] M. Habib, P. Peroche, Some problems about linear arboricity, Discrete
Math. 41 (1982),219-220.
[31] R. Haggkvist, A lemma on cycle decompositions, Ann. Discrete Math. 27
(1985),227-232.
[32] R. Haggkvist, Factors and path decompositions, Research report, No 13,
Dept. Math., Umea University. (2001).
[33] S. L. Hakimi, J. Mitchem and E. Schmeichel, Star Arboricity of Graphs,
Discrete Math. 149 (1996),93-98.
[34] H. Hanani, Balanced incomplete block designs, Discrete Math. 4
(1975),255-369.
[35] F. Harary, Covering and packing in graphs I, Ann. New York Acad. Sci.
175 (1970)198-205.
[36] K. Heinrich, J. Liu and M. Yu, P4-decompositions of regular graphs, J.
Graph Theory 31 (1999),135-143.
[37] K. Heinrich, J. Liu and C.Q. Zhang, Triangle-free circuit decompositions
and Petersen minors, J. Combin. Theory, Ser. B 72 (1998),197-207.
[38] A. W. Hilton, C. A. Rodger, Hamiltonian decompositions of complete
regular s-partite graphs, Discrete Math. 58(1986),63-78.
[39] J. D. Horton, Resolvable path designs, J. Combin. Theory, Ser. A 39
(1985),117-131.
[40] C. Huang, On Handcuffed designs, Research Report CORR75-10, University
of Waterloo.
[41] C. Huang and A. Rosa, On the existence of balanced bipartite designs,
Utilitas Math. 4 (1973)55-75.
[42] C. Huang, On the existence of balanced bipartite designs II, Discrete
Math. 9 (1974)147-159.
[43] C. Huang, Resolvable balanced bipartite designs, Discrete Math. 14
(1976),319-335.
[44] S. H. Y. Hung and N. S. Mendelsohn, Handcuffed designs, Discrete Math.
18 (1977),23-33.
[45] B. W. Jackson, Some cycle decompositions of complete graphs, Journal
of Combinatorics, Information and System Sciences 13 (1988),20-32.
[46] M. S. Jacobson, M. Truszczy´nski, and Z. Truza, Decompositions of regular
bipartite graphs, Discrete Math. 89 (1991),17-27.
[47] A. Kotzig, From the theory of finite regular graphs of degree three and
four, ˇ Casopis Pˇest Mat 82 (1957),76-92.
[48] M. Kouider and Z. Lonc, Path decompositions and perfect path double
covers, Australa. J. Combin. 19 (1999),261-274.
[49] C. S. Kumar, On P4−decomposition of graphs, Taiwanese J. of Math. 7
(2003),657-664.
[50] R. Laskar, B. Auerback, On decomposition of r-partite graphs into edgedisjoint
Hamilton circuits, Discrete Math.14 (1976),265-268.