Packing and Covering Complete Graphs with 3- and 4-paths

完全圖之3路徑及4路徑充填與覆蓋

10.29850/LTJ.201112.0009

李鴻志(Hung-Chih Lee)；陳薇琳(Wei-Lin Chen)

完全圖 ； 路徑 ； 充填 ； 覆蓋 ； 餘圖 ； 填補圖 ； complete graph ； path ； packing ； covering ； leave ； padding

嶺東學報

30期（2011 / 12 / 01）

227 - 240

英文

k路徑是長度為k之路徑。本文探討完全圖之3路徑及4路徑充填與覆蓋問題，且得到所有最大充填與最小覆蓋。

A k-path is a path of length k. In this paper, we completely solve the problem of finding maximum packings and minimum coverings of complete graphs with k-paths for k belong to {3,4}.

1. Adams, P.,Bryant, D. E.,El-Zanati, S. I.(1999).Packing and covering the complete graph with cubes.Australas. J. Combin.,20,267-288.
2. Billington, E. J.,Lindner, C. C.(1998).Maximum packings of bowtie designs.J. Combin. Math. Combin. Comput.,27,227-249.
3. Bondy, J. A.,Murty, U. S. R.(1976).Graph Theory with Applications.London:Macmillan Press.
4. Brouwer, A. E.(1979).Optimal packings of Kn into K4's.J. Combin. Theory Ser. A,26,278-297.
5. Bryant, D.,Horsley, D.(2008).Packing cycles in complete graphs.J. Combin. Theory Ser. B,98,1014-1037.
6. El-Zanati, S. I.(1994).Maximum packings with odd cycles.Discrete Math.,131,91-97.
7. Fort, M. K. Jr.,Hedlund, G. A.(1958).Minimal coverings of pairs by triples.Pacific J. Math.,8,709-719.
8. Grinstead, C. M.(1977).On coverings and packings of the complete graph with cycles.Ars Combin.,3,25-37.
9. Hoffman, D. G.,Lindner, C. C.,Sharry, M. J.,Street, A. P.(1996).Maximum packings of Kn with copies of K4-e.Aequationes Math.,51,247-269.
10. Hoffman, D. G.,Wallis, W. D.(1991).Packing complete graphs with squares.Bull. ICA,1,89-92.
11. Li, M.,Huo, J.,Gao, Z.(2009).Maximum packings and minimal coverings of kv with octagons.Graphs Combin.,25,735-752.
12. Lin, J.-J.(2010).Maximum packings of complete graphs with octagons.Ars Combin.,97,479-495.
13. Lindner, C. C.,Street, A. P.(1997).Multiple minimum coverings of Kn with copies of K4-e.Utilitas Math.,52,223-239.
14. Lindner, C. C.,Street, A. P.(1996).Simple minimum coverings of Kn with copies of K4-e.Aequationes Math.,52,284-301.
15. Milici, S.,(2004).Coverings of a complete graph with five-vertex and five-edge graphs.Discrete Math.,284,225-229.
16. Mills, W. M.(1973).On the covering of pairs by quadruples-II.J. Combin. Theory,15,138-166.
17. Mills, W. M.(1972).On the covering of pairs by quadruples-I.J. Combin. Theory,13,55-78.
18. Parker, C. A.(1998).Auburn, Alabama,Auburn University.
19. Roditty, Y.(1983).Packing and covering of the complete graph with a graph G of four vertices or less.J. Combin. Theory Ser. A,34,231-243.
20. Roditty, Y.(1993).Packing and covering of the complete graph. IV. The trees of order seven.ARS Combin.,35,33-64.
21. Rosa, A.,Znám, S.(1994).Packing pentagons into complete graphs: How clumsy can you get?.Discrete Math.,128,305-316.
22. Schönheim, J.(1966).On maximal systems of k-tuples.Studia. Sci. Math. Hung.,1,363-368.
23. Schönheim, J.,Bialostocki, A.(1975).Packing and covering the complete graph with 4-cycles.Canad. Math. Bull.,18,703-708.
24. Stanton, R. G.,Rogers, M. J.(1982).Packings and coverings by triples.ARS Combin.,13,61-69.
25. Tarsi, M.(1983).Decomposition of a complete multigraph into simple paths: non-balanced handcuffed designs.J. Combin. Theory Ser. A,34,60-70.