Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Nonisomorphic Maximum Packing and Minimum Covering of K v with 8-Cycles

  • Original Paper
  • Published:
Graphs and Combinatorics Aims and scope Submit manuscript

Abstract

The maximum packing C 8-max PD(v) and minimum covering C 8-minCD(v) of K v with 8-cycles are studied, all structures with the nonisomorphic leave (excess) are presented. In Li et al. (Graphs Combin 25:735–752, 2009), C 8-max PD(v) and C 8-minCD(v) have been determined for odd v. In this paper, we introduce the enumeration of nonisomorphic \({(v,\frac{v}{2}+s)}\)-graphs (s = 4, 6), give complete solution of the maximum packing and minimum covering designs of K v with 8-cycles for any even v with all possible leaves (excesses).

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Alspach B., Gavlas H.: Cycle decompositions of K n and K n − I, J. Combin. Theory Ser. B 81, 77–99 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  2. Billington E., Fu H., Rodger C.: Packing λ-fold complete multipartite graphs with 4-cycles. Graphs Combin. 21, 169–185 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  3. Harary F.: Graph Theory. Addison-Wesley, Reading (1969)

    Google Scholar 

  4. Kennedy J.: Maximum packings of K n with hexagons. Australas. J. Combin. 7, 101–110 (1993) Corrigendum: ibid 10, 293 (1994)

    MathSciNet  MATH  Google Scholar 

  5. Kennedy J.: Minimum coverings of K n with hexagons. Australas. J. Combin. 16, 295–303 (1997)

    MathSciNet  MATH  Google Scholar 

  6. Kang Q.: A Note on Combinatorics. Science Press, Beijing (2009)

    Google Scholar 

  7. Li M., Huo J., Gao Z.: Maximum packings and minimum coverings of K v with octagons. Graphs Combin. 25, 735–752 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  8. Sotteau D.: Decompositions of K m,n \({(K_{m,n}^{*})}\) into cycles (circuits) of length 2k. J. Combin. Theory Ser. B 30, 75–81 (1981)

    Article  MathSciNet  MATH  Google Scholar 

  9. Schönheim J., Bialostocki A.: Packing and covering of the complete graph with 4-cycles. Can. Math. Bull. 18, 703–708 (1975)

    Article  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Institute of Mathematics, Hebei Normal University, Shijiazhuang, 050016, People’s Republic of China

    Qingde Kang

  2. Department of Mathematics, Hebei University of Engineering, Handan, 056038, People’s Republic of China

    Mingchao Li & Jingjing Huo

Authors
  1. Qingde Kang
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Mingchao Li
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Jingjing Huo
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Qingde Kang.

Additional information

Research supported by NSFC Grant 10971051 and NSFHB A2010000353.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Kang, Q., Li, M. & Huo, J. Nonisomorphic Maximum Packing and Minimum Covering of K v with 8-Cycles. Graphs and Combinatorics 29, 1007–1040 (2013). https://doi.org/10.1007/s00373-012-1167-x

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00373-012-1167-x

Keywords

Search

Navigation