Packing and Covering Multicrowns with 4-cycles

多重邊皇冠圖之4迴圈充填與覆蓋

10.29850/LTJ.201212.0001

李鴻志(Hung-Chih Lee)；姚美玉(Mei-Yu Yao)

多重邊皇冠圖 ； 迴圈 ； 充填 ； 覆蓋 ； 餘圖 ； 填補圖 ； multicrown ； cycle ； packing ； covering ； leave ； padding

嶺東學報

32期（2012 / 12 / 01）

1 - 17

英文

多重邊皇冠圖λCn,n-1是點集為{a0, a1, ..., an-1, b0, b1,...,bn-1}，而邊集為{aibj (λ重邊) : i = 0,1,...,n-1, j≡i +1, i+2,...,i+n-1 (mod n)}之重邊二部圖。k迴圈是長度為k之迴圈。本文探討多重邊皇冠圖之4迴圈充填與覆蓋問題，且得到所有最大充填與最小覆蓋。

A k-cycle is a cycle of length k. The multicrown λCn,n-1 is the multigraph with vertex set {a0, a1, ..., an-1, b0, b1, ..., bn-1} and edge set {aibj with multiplicity λ: i = 0,1,...,n-1, j≡i + 1,i + 2,...,n -1 (mod n)}. In this paper, we completely solve the problem of finding maximum packings and minimum coverings of multicrowns with 4-cycles.

1. Billington, E. J.,Fu, H.-L.,Rodger, C. A.(2001).Packing complete multipartite graphs with 4-cycles.Journal of Combinatorial Designs,9,107-127.
2. Billington, E. J.,Fu, H.-L.,Rodger, C. A.(2005).Packing λ-fold complete multipartite graphs with 4-cycles.Graphs and Combinatorics,21,169-185.
3. Billington, E. J.,Lindner, C. C.(1996).Maximum packings of uniform group divisible triple systems.Journal of Combinatorial Designs,4,397-404.
4. Bondy, J. A.,Murty, U. S. R.(1976).Graph Theory with Applications.London:Macmillan Press.
5. Brown, L.,Coker, G.,Gardner, R.,Kennedy, J.(2005).Packing the complete bipartite graph with hexagons.Congressus Numerantium,174,97-106.
6. Fort, M. K. ,Hedlund, G. A.(1958).Minimal coverings of pairs by triples.Pacific Journal of Mathematics,8(4),709-719.
7. Fu, H.-L.,Huang, M.-H.(2004).Packing balanced complete multipartite graphs with hexagons.Ars Combinatoria,71,49-64.
8. Gardner, R.,LaVoie, S.,Nguyen, C.(2010).4-cycle coverings of the complete graph with a hole.International Journal of Pure and Applied Mathematics,64,317-330.
9. Hoffman, D. G.,Wallis, W. D.(1991).Packing complete graphs with squares.Bulletin of the Institute of Combinatorics and its Applications,1,89-92.
10. Huang, M.-H.,Fu, C.-M.,Fu, H.-L.(2007).Packing 5-cycles into balanced complete m-partite graphs for odd m.Journal of Combinatorial Optimization,14,323-329.
11. Kennedy, J. A.(1997).Minimum coverings of Kn with hexagons.The Australasian Journal of Combinatorics,16,295-303.
12. Kennedy, J. A.(1993).Maximum packings of Kn with hexagons.The Australasian Journal of Combinatorics,7,101-110.
13. Li, M.,Huo, J.,Gao, Z.(2009).Maximum packings and minimal coverings of with octagons.Graphs and Combinatorics,25,735-752.
14. Lin, J.-J.(2010).Maximum packings of complete graphs with octagons.Ars Combinatoria,97,479-495.
15. Ma, J.,Pu, L.,Shen, H.(2006).Cycle decompositions of Kn.n-i.SIAM Journal on Discrete Mathematics,20,603-609.
16. Mills, W. M.(1973).On the covering of pairs by quadruples-ii.Journal of Combinatorial Theory,15,138-166.
17. Mills, W. M.(1972).On the covering of pairs by quadruples-i.Journal of Combinatorial Theory,13,55-78.
18. Rosa, A.,Znám, S.(1994).Packing pentagons into complete graphs: how clumsy can you get?.Discrete Mathematics,128,305-316.
19. Schönheim, J.(1966).On maximal systems of k-tuples.Studia Scientiarum Mathematicarum Hungarica,1,363-368.
20. Schönheim, J.,Bialostocki, A.(1975).Packing and covering of the complete graph with 4-cycles.Canadian Mathematical Bulletin,18,703-708.
21. Sotteau, D.(1981).Decomposition of km,n ( k*m,n ) into cycles (circuits) of length 2k.Journal of Combinatorial Theory, Series B,30,75-81.
22. Stanton, R. G.,Rogers, M. J.(1982).Packings and coverings by triples.Ars Combinatoria,13,61-69.