跳到主要內容

臺灣博碩士論文加值系統

(23.20.20.52) 您好!臺灣時間:2022/01/24 18:28
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:黃明輝
研究生(外文):Ming-Hway Huang
論文名稱:圖的圈填充之研究
論文名稱(外文):Packing Graphs with Cycles
指導教授:傅恆霖
指導教授(外文):Hung-Lin Fu
學位類別:博士
校院名稱:國立交通大學
系所名稱:應用數學系
學門:數學及統計學門
學類:數學學類
論文種類:學術論文
論文出版年:2002
畢業學年度:90
語文別:英文
論文頁數:60
中文關鍵詞:圈填充覆蓋5圈6圈完全多部分圖卡笛森運算
外文關鍵詞:packingcycle packingmultipartite graphCartesian product5-cycles6-cycles
相關次數:
  • 被引用被引用:0
  • 點閱點閱:139
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
一個圖G的k圈填充是圖G邊中不互相相同的k圈集合。然而並不是所有的圖都可以被k圈填充,我們將剩下的邊集合所導出的子圖稱為這個裝填的殘留。能夠將殘留的部分邊數最少的裝填又稱為是最大的裝填。此時殘留的部分自然是最小殘留。
對應於裝填的觀念,我們也可考慮用k圈來覆蓋圖G。不夠的部分需加一些補丁,
如果補丁所用的邊數為最少,則此為最小覆蓋。
研究填充與覆蓋的問題已有百多年的歷史了,而最有名的題目就是完全圖的3圈填充。在此論文中我們著眼於5圈及 6圈的填充而考慮的圖形為平衡的完全多部分圖及兩個完全圖的卡笛森運算。
A $k$-$cycle$ $packing$ of a graph $G$ is a set of edge-disjoint
$k$-cycles in $G$. A $k$-cycle packing $C$ is $maximum$ if
$|C|\geq |C''|$ for all other $k$-cycle packings $C''$ of $G$. The
$leave$ $L$ of a packing $C$ is the subgraph induced by the set of
edges of $G$ that does not occur in any $k$-cycle of the packing
$C$. Therefore a maximum packing has a minimum leave.
A $k$-$cycle$ $covering$ of $G$ is a set of edge-disjoint
$k$-cycles $\mathcal{C}$ such that each edge of $E(G)$ occurs in
at least one $k$-cycle in $\mathcal{C}$. A $k$-cycle covering
$\mathcal{C}$ is $minimum$ if $|\mathcal{C}|\leq |\mathcal{C''}|$
for all other $k$-cycle coverings of $G$. The graph induced by the
set of edges which are added to $G$ in the covering is called the
$padding$ of the covering. Clearly, a minimum padding can be
obtained in a minimum covering.
The study of packing and covering problem commenced more than one
hundred years ago. The most famous one is a $3$-cycle packing
(respectively, covering) of the complete graph $K_{v}$. In case
that the leave of a 3-cycle packing is an empty graph, we have a
Steiner triple system of order $v$. It is indeed very closely
related to the study of combinatorial designs.
In this thesis, we shall focus on the study of 5-cycle and 6-cycle
packings (respectively, coverings). By considering $G$ as the
balanced complete multipartite graphs $K_{m(n)}$ and the Cartesian
product of two complete graphs $K_{m}\times K_{n}$, we have
obtained several results which will be presented in chatpers two
to six.
Abstract i
Contents iii
1 Introduction 1
1.1 Motavation 1
1.2 The preliminaries in Graph Theory 3
1.3 The preliminaries in Combinatorial Design 5
1.4 Some results in cycle packing 8
2 Packing $K_{m(n)}$ with $5$-cycles 10
3 Packing $K_{m(n)}$ with $6$-cycles 17
4 Packing $K_{m}\times K_{n}$ with 5-cycles 28
5 Packing $K_{m}\times K_{n}$ with 6-cycles 36
6 Minimum covering 42
6.1 Covering $K_{m}\times K_{n}$ with 5-cycles 43
6.2 Covering $K_{m(n)}$ and $K_{m}\times K_{n}$ with 6-cycles 45
Conclusion 50
Bibliography 51
\bibitem{chow1}\label{chow1}
P. Adams, D. E. Bryant, and A. Khodkar, 3,5-cycle Decompositions,
J. Combin. Des. 6 (1998), no. 2, 91--110.
\bibitem{chow2}\label{chow2}
B. Alspach and H. Gavlas, Cycle decompositions of $K\sb n$ and
$K\sb n-I$, J. Combin. Theory Ser. B 81 (2001), no. 1, 77--99.
\bibitem{chow3}\label{chow3}
B. Alspach and S. Marshall, Even cycle decompositions of complete
graphs minus a $1$-factor, J. Combin. Des. 2 (1994), no. 6,
441--458.
\bibitem{chow4}\label{chow4}
B. Alspach and B. N. Varma, Decomposing complete graphs into
cycles of length $2p\sp{e}$, Ann. Discrete Math. 9 (1980),
155--162.
\bibitem{chow5}\label{chow5}
I. Anderson, Combinatorial Designs: Construction Methods, England,
1990.
\bibitem{chow6}\label{chow6}
D. J. Ashe, C. A. Rodger, and H. L. Fu, All 2-regular leaves of
partial 6-cycles system, in preprints.
\bibitem{chow7}\label{chow7}
E. Bell, Decomposition of a complete graph into cycles of length
less than or equal to 50. M. Sc. Thesis, Auburn University, 1991.
\bibitem{chow8}\label{chow8}
J. C. Bermond, C. Huang, and D. Sotteau, Balanced cycle and
circuit designs: Even cases, Ars Combin. 5(1978), 293--318.
\bibitem{chow9}\label{chow9}
J. C. Bermond, and D. Sotteau, Balanced cycle and circuit designs:
Odd cases. Proc. Colloq. Oberhof Illmenau, (1978), 11--32.
\bibitem{chow10}\label{chow10}
E. J. Billington, H-L. Fu and C. A. Rodger, Packing complete
multipartite graphs with 4-cycles, J. Combin. Des. {\bf 9} (2001),
107--127.
\bibitem{chow11}\label{chow11}
E. J. Billington, H-L. Fu and C. A. Rodger, Packing $\lambda$-fold
complete multipartite graphs with 4-cycles, in preprints.
\bibitem{chow12}\label{chow12}
D. Bryant and A. Khodkar, Maximum packings of $K\sb v-K\sb u$ with
triples, Ars Combin. {\bf 55} (2000), 259--270.
\bibitem{chow13}\label{chow13}
N. J. Cavenagh and E. J. Billington, Decompositions of complete
multipartite graphs into cycles of even length, Graphs and
Combinatorics. {\bf 16} (2000), 49--65.
\bibitem{chow14}\label{chow14}
N. J. Cavenagh and E. J. Billington, On decomposing complete
tripartite graphs into 5-cycles, Australas. J. Combin. 22 (2000),
41--62
\bibitem{chow15}\label{chow15}
Kelda A. Farrell and David A. Pike, 6-Cycle decomposions of the
cartesian product of two complete graphs, Utilitas Mathematica, to
appear.
\bibitem{chow16}\label{chow16}
H. L. Fu, C. C. Lindner, and C. A. Rodger, The Doyen-Wilson
Theorem for Minimum Coverings with triples, J. Combin. Des. {\bf
5} (1997), 341--352.
\bibitem{chow17}\label{chow17}
H. Hanani, The existence and construction of balanced incomplete
block designs, Ann. Math. Statist. 32(1961), 361--386.
\bibitem{chow18}\label{chow18}
C. Huang, and A. Rosa. On the existence of balanced bipartite
designs, Utillitas Math. 4(1973), 55--75.
\bibitem{chow19}\label{chow19} J. A.\ Kennedy,
Maximum packings of $K_{n}$ with hexagons, Australas. J.
Combin.{\bf 7} (1993), 101--110. Corrigendum: ibid {\bf 10}
(1994), 293.
\bibitem{chow20}\label{chow20}
Rev. T. P. Kirkman, On the problem in combinations, Cambr. and
Dublin Math. J. 2(1847), 191--204.
\bibitem{chow21}\label{chow21}
A. Kotzig. On decompositions of the complete graph into $4k$-gons,
Mat.-Fyz. cas. 15 (1965), 227--233.
\bibitem{chow22}\label{chow22}
C. C. Lindner and C. A. Rodger, ''Decomposition into cycles II:
Cycle systems" in Contemporary design theory: a collection of
surveys, J. H. Dinitz and D. R. Stinson(Editors), Wiley, New York,
1992, 325--369.
\bibitem{chow23}\label{chow23}
D. E. Lucas, R\''{e}cr\''{e}ations Math\''{e}matiques, vol. 2,
Gauthiers Villars, Pairs, 1892.
\bibitem{chow24}\label{chow24}
A. Rosa, On cyclic decompositions of the complete graph into
(4m+2)gons, Mat.-Fyz. Cas. 16(1966), 349--352.
\bibitem{chow25}\label{chow25}
A. Rosa and C. Huang, Another class of balanced graph design:
balanced circuit designs, Discrete Math. 12(1975), 269--293.
\bibitem{chowa}\label{chowa} A. Rosa and S. Zn\''{a}m,
Packing pentagons into complete graphs: how clumsy can you get?
Discrete Math. 128 (1994), no. 1-3, 305--316.
\bibitem{chow26}\label{chow26}
D. B. West, Introduction to Graph Theory, New Jersey (1996).
\bibitem{chow27}\label{chow27}
R. M. Wilson, Some partitions of all triples into Steiner triple
systems, Lecture Notes in Math. 411, Springer, Berlin, (1974),
267-277.
%\bibitem{chow9}\label{chow10}
%C. C. Lindner and C. A. Rodger, "Design Theory", CRC, Boca Raton,
%New York, 1997, 14--17.
\bibitem{chow28}\label{chow28}
W. Sajna, Cycle decompositions of $K_{n}$ and $K_{n}-I$, Ph.D.
Thesis, Simon Fraser University, July 1999.
\bibitem{chow29}\label{chow29}
D. Sotteau, Decomposition of $K_{m,n}(K_{m,n}^{*})$ into cycles
(circuit) of length 2$k$, J. Combin. Theory(ser. B) {\bf 30}
(1981), 75--81.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top