Packing and Covering of the Complete Graph with 4-Cycles*

J. Schönheim; A. Bialostocki

doi:10.4153/CMB-1975-123-4

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

The maximal number of pairwise edge disjoint 4-cycles in the complete graph Kn and the minimal number of 4-cycles whose union is Kn are determined.

Footnotes

This research was supported in part by N.R.C. grant #A5198.

References

1. Beineke, L. W., A survey of packings and coverings of graphs. The Many Facets of Graph Theory. Ed. Chartrand, G. and Kapoor, S. F.. Berlin, Heidelberg, New York 1969, p. 45.Google Scholar

2. Beineke, L. W., Packings of bipartite graphs. (To appear.)Google Scholar

3. Chartrand, G., Geller, D. and Hedetniemi, S., Graphs with forbidden subgraphs. J. Combinatorial Theory B. 10 (1971) 12–41.Google Scholar

4. Fort, M. K. Jr, and Hedlund, G. A., Minimal coverings of pairs by triples. Pacific Journal Math. 8 (1958) 709–719.Google Scholar

5. Schönheim, J., On maximal systems of k-tuples. Studia Sci. Math. Hungarica (1966) 363–368.Google Scholar

6. Hanani, H., The existence and construction of balanced incomplete block designs. Annals of Math. Statistics 6 (1961) 362–386.Google Scholar

7. Kotzig, A., On decompositions of the complete graph into 4k-gons. (In Russian). Mat.-fyz. casopis SAV 15 (1965), 229–232.Google Scholar

8. Rosa, A., O cyklickych rozkladoch komletneho grafu na neparnouholniky. Cas. pest. mat. 91 (1966) 53–63.Google Scholar

Crossref Citations

This article has been cited by the following publications. This list is generated based on data provided by Crossref.

Schönheim, J. 1975. Partition of the edges of the directed complete graph into 4-cycles. Discrete Mathematics, Vol. 11, Issue. 1, p. 67.

Roditty, Y 1983. Packing and covering of the complete graph with a graph G of four vertices or less. Journal of Combinatorial Theory, Series A, Vol. 34, Issue. 2, p. 231.

Caro, Yair and Yuster, Raphael 1998. Covering Graphs: The Covering Problem Solved. Journal of Combinatorial Theory, Series A, Vol. 83, Issue. 2, p. 273.

Fu, H.-L. and Lindner, C.C. 1998. The Doyen-Wilson theorem for maximum packings of Kn with 4-cycles. Discrete Mathematics, Vol. 183, Issue. 1-3, p. 103.

Billington, Elizabeth J. Fu, Hung-Lin and Rodger, C.A. 2001. Packing complete multipartite graphs with 4-cycles. Journal of Combinatorial Designs, Vol. 9, Issue. 2, p. 107.

Zhang, Shucheng and Yin, Jianxing 2002. Packing of Kv with certain graphs of five vertices. Journal of Statistical Planning and Inference, Vol. 106, Issue. 1-2, p. 387.

Milici, Salvatore 2004. Coverings of a complete graph with five-vertex and five-edge graphs. Discrete Mathematics, Vol. 284, Issue. 1-3, p. 225.

Adams, Peter Bryant, Darryn and Maenhaut, Barbara 2004. Common multiples of complete graphs and a 4-cycle. Discrete Mathematics, Vol. 275, Issue. 1-3, p. 289.

Kang, Qingde Zhang, Yanfang and Zuo, Huijuan 2004. Packings and coverings of λKv by k-circuits with one chord. Discrete Mathematics, Vol. 279, Issue. 1-3, p. 287.

Bryant, Darryn and Horsley, Daniel 2008. Packing cycles in complete graphs. Journal of Combinatorial Theory, Series B, Vol. 98, Issue. 5, p. 1014.

Li, Mingchao Huo, Jingjing and Gao, Zhichao 2009. Maximum Packings and Minimum Coverings of K v with Octagons. Graphs and Combinatorics, Vol. 25, Issue. 5, p. 735.

Newman, N. A. and Rodger, C. A. 2010. Enclosings of λ-fold 4-cycle systems. Designs, Codes and Cryptography, Vol. 55, Issue. 2-3, p. 297.

Billington, Elizabeth J. Dejter, Italo J. Hoffman, D. G. and Lindner, C. C. 2011. Almost Resolvable Maximum Packings of Complete Graphs with 4-Cycles. Graphs and Combinatorics, Vol. 27, Issue. 2, p. 161.

Horsley, Daniel 2011. Maximum packings of the complete graph with uniform length cycles. Journal of Graph Theory, Vol. 68, Issue. 1, p. 1.

Coker, Brandon Coker, Gary D. Gardner, Robert and Xia, Yan 2013. Packings and Coverings of Various Complete Graphs with the 4-Cycle with a Pendant Edge. ISRN Combinatorics, Vol. 2013, Issue. , p. 1.

Kang, Qingde Li, Mingchao and Huo, Jingjing 2013. Nonisomorphic Maximum Packing and Minimum Covering of K v with 8-Cycles. Graphs and Combinatorics, Vol. 29, Issue. 4, p. 1007.

Zhou, Min and Cao, Haitao 2015. Almost resolvable maximum packings of complete graphs with 5-cycles. Frontiers of Mathematics in China, Vol. 10, Issue. 2, p. 461.

Liang, Zhihe Zuo, Huijuan and Miao, Yulian 2015. Packings and Coverings of the Complete Bipartite Graph by Octagons. Journal of Discrete Mathematical Sciences and Cryptography, Vol. 18, Issue. 1-2, p. 17.

Aydinian, Harout 2017. A subspace covering problem in the n-cube. Discrete Applied Mathematics, Vol. 216, Issue. , p. 513.

Article contents

Packing and Covering of the Complete Graph with 4-Cycles*

Abstract

Footnotes

References

Save article to Kindle

Save article to Dropbox

Save article to Google Drive

Reply to: Submit a response

Your details

You have entered the maximum number of contributors

Conflicting interests