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

Decomposition of a Complete Bipartite Multigraph into Arbitrary Cycle Sizes

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

Abstract

In a graph G, let \(\mu _G(xy)\) denote the number of edges between x and y in G. Let \(\lambda K_{v,u}\) be the graph \((V\cup U,E)\) with \(|V|=v\), \(|U|=u\), and

$$\begin{aligned} \mu _G{(xy)}={\left\{ \begin{array}{ll} \lambda &{}\text{ if }\,\, x\in U \text{ and }\,\, y\in V \text{ or } \text{ if }\,\, x\in V \text{ and }\,\, y\in U\\ 0 &{}\text{ otherwise. } \\ \end{array}\right. } \end{aligned}$$

Let M be the sequence of non-negative integers \(m_1,m_2,\ldots ,m_n\). An (M)-cycle decomposition of a graph G is a partition of the edge set into cycles of lengths \(m_1,m_2,\ldots ,m_n\). In this paper, we establish some necessary and some sufficient conditions for the existence of an (M)-cycle decomposition of \(\lambda K_{v,u}\).

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. Bahmanian, M.A., Šajna, M.: Decomposing complete equipartite multigraphs into cycles of variable lengths: the amalgamation-detachment approach. J. Comb. Des. 24(4), 165–183 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  2. Bryant, D.: Packing paths in complete graphs. J. Comb. Theory Ser. B 100(2), 206–215 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  3. Bryant, D., Horsley, D.: Packing cycles in complete graphs. J. Comb. Theory Ser. B 98(5), 1014–1037 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  4. Bryant, D., Horsley, D.: Decompositions of complete graphs into long cycles. Bull. Lond. Math. Soc. 41(5), 927–934 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  5. Bryant, D., Horsley, D.: An asymptotic solution to the cycle decomposition problem for complete graphs. J. Comb. Theory Ser. A 117(8), 1258–1284 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  6. Bryant, D., Horsley, D., Maenhaut, B.: Decompositions into 2-regular subgraphs and equitable partial cycle decompositions. J. Comb. Theory Ser. B 93(1), 67–72 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  7. Bryant, D., Horsley, D., Maenhaut, B., Smith, B.R.: Cycle decompositions of complete multigraphs. J. Comb. Des. 19(1), 42–69 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  8. Bryant, D., Horsley, D., Maenhaut, B., Smith, B.R.: Decompositions of complete multigraphs into cycles of varying lengths. arXiv preprint arXiv:1508.00645 (2015)

  9. Bryant, D., Horsley, D., Pettersson, W.: Cycle decompositions V: complete graphs into cycles of arbitrary lengths. Proc. Lond. Math. Soc. 108(5), 1153–1192 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  10. Horsley, D.: Decomposing various graphs into short even-length cycles. Ann. Comb. 16(3), 571–589 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  11. Horsley, D., Hoyte, R.A.: Doyen–wilson results for odd length cycle systems. J. Comb. Des. 24(7), 308–335 (2016)

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

    Article  MATH  Google Scholar 

Download references

Acknowledgements

We would like to thank the referees for their contributions that helped polish this paper.

Author information

Authors and Affiliations

  1. Dalton State College, Dalton, GA, 30720, USA

    John Asplund

  2. Kaiser Permanente, Atlanta, GA, 30305, USA

    Joe Chaffee

  3. Cedar Crest College, Allentown, PA, 18104, USA

    James M. Hammer

Authors
  1. John Asplund
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Joe Chaffee
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. James M. Hammer
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to James M. Hammer.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Asplund, J., Chaffee, J. & Hammer, J.M. Decomposition of a Complete Bipartite Multigraph into Arbitrary Cycle Sizes. Graphs and Combinatorics 33, 715–728 (2017). https://doi.org/10.1007/s00373-017-1817-0

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00373-017-1817-0

Keywords

Search

Navigation