圖形的路徑分解,迴路分解和星形分解

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：29

、訪客IP：18.191.171.20

姓名

李明茹(Ming-Ju Lee) 查詢紙本館藏

畢業系所

數學系

論文名稱

圖形的路徑分解,迴路分解和星形分解
(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
★ 圖形之分割與反魔標號

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

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

摘要(中)

圖形分解是圖形理論中的一個非常重要的主題，因為許多數學結
構與圖形分解有相當緊密的聯結，而且圖形分解的結果可以廣泛的應用
到其他的領域。因子分解(factorization)是一種特殊型態的圖形分
解，其與組合設計(combinatorial design)有密不可分的關係。我們有
許多類型的分解問題，例如星型分解(star decomposition)、路徑分解
(path decomposition)、迴路分解(cycle decomposition)、完全二部
圖分解(complete bipartite decomposition)等等。直到今日，上述分
解依然是熱門討論話題。
在本篇論文中，某些有向圖的反向迴路(antidirected cycle)分
解和有向路徑分解與某些圖形的毛毛蟲因子分解(caterpillar
factorization)的問題將被探討。圖形分解與圖形的蔭度(arboricity)
有著多樣且緊密的關係。本論文，我們同時會討論某些圖形的線性蔭度
(linear arboricity)與星形蔭度(star arboricity)。
本論文將分為七個章節來做探討。第一章將介紹基本的定義與符
號。第二章為探討圖形的路徑分解。首先，我們為完全三部多重邊圖的
同構路徑分解給定一個充分必要條件。接著探討完全三部多重有向邊圖
的同構有向路徑分解。第三章將對完全對稱圖形的反向迴路分解的存在
給定一個充分必要條件。第四章將對完全對稱圖形減去一因子
(one-factor)的反向迴路分解的存在給定一個充分必要條件。第五章將
討論皇冠圖(crown)中毛毛蟲的因子分解。首先給予在皇冠圖中均衡的
毛毛蟲因子分解一個充分必要條件。接著再給予在對稱皇冠圖中，有向
毛毛蟲因子分解的充分必要條件。第六章，首先考慮皇冠圖的星形蔭度
問題。先給定一個下界。接著探討在某些特定皇冠圖的星形蔭度。第七
章，我們考慮在某些特定k當中，完全圖的長度為k的線性蔭度(linear
k-arboricity)問題。

摘要(英)

Graph decomposition is an important subject of graph theory since many
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 Introduction 1
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

參考文獻

[1] J. Akiyama, Three developing topics in graph theory, Doctoral Dissertation,
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.

指導教授

林強(Chiang Lin)

審核日期

2007-7-11

推文