Cut-Edges and Regular Factors in Regular Graphs of Odd Degree | Graphs and Combinatorics Skip to main content
Springer Nature Link
Log in

Cut-Edges and Regular Factors in Regular Graphs of Odd Degree

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

Abstract

We study 2k-factors in \((2r+1)\)-regular graphs. Hanson, Loten, and Toft proved that every \((2r+1)\)-regular graph with at most 2r cut-edges has a 2-factor. We generalize their result by proving for \(k\le (2r+1)/3\) that every \((2r+1)\)-regular graph with at most \(2r-3(k-1)\) cut-edges has a 2k-factor. Both the restriction on k and the restriction on the number of cut-edges are sharp. We characterize the graphs that have exactly \(2r-3(k-1)+1\) cut-edges but no 2k-factor. For \(k>(2r+1)/3\), there are graphs without cut-edges that have no 2k-factor, as studied by Bollobás, Saito, and Wormald.

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
¥17,985 /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 includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2

Similar content being viewed by others

References

  1. Akiyama, J., Kano, M.: Factors and factorizations of graphs—a survey. J. Graph Theory 9, 1–42 (1985)

    MathSciNet  MATH  Google Scholar 

  2. Akiyama, J., Kano, M.: Factors and factorizations of graphs: proof techniques in factor theory. Lecture Notes in Mathematics, vol. 2031. Springer, Heidelberg (2011)

  3. Baebler, F.: Über die Zerlegung regulärer Streckenkromplexe ungerader Ordnung (German). Comment. Math. Helv. 10, 275–287 (1937–1938)

  4. Belck, H.-B.: Reguläre Faktoren von Graphen (German). J. Reine Angew. Math. 188, 228–252 (1950)

    MathSciNet  MATH  Google Scholar 

  5. Berge, C.: Graphs and hypergraphs (North-Holland, 1973): (translation and revision of Graphes et Hypergraphes, Dunod, 1970), p. 162 (1973)

  6. Bollobás, B., Saito, A., Wormald, N.C.: Regular factors of regular graphs. J. Graph Theory 9, 97–103 (1985)

    MathSciNet  MATH  Google Scholar 

  7. Häggkvist, R.: Factors galore: extending theorems of Petersen, Baebler, Belck and Gallai, lecture at “Combinatorics in Cambridge”, August 4, 2003 (2003)

  8. Hanson, D., Loten, C.O.M., Toft, B.: On interval colourings of bi-regular bipartite graphs. ARS Combin. 50, 23–32 (1998)

    MathSciNet  MATH  Google Scholar 

  9. Katerinis, P.: Maximum matchings in a regular graph of specified connectivity and bounded order. J. Graph Theory 11, 53–58 (1987)

    MathSciNet  MATH  Google Scholar 

  10. Niessen, T., Randerath, B.: Regular factors of simple regular graphs and factor-spectra. Discrete Math. 185, 89–103 (1998)

    MathSciNet  MATH  Google Scholar 

  11. Petersen, J.: Die Theorie der regulären graphs. Acta Math. 15, 193–220 (1891)

    MathSciNet  MATH  Google Scholar 

  12. Plesník, J.: Connectivity of regular graphs and the existence of 1-factors. Mat. Casopis Sloven. Akad. Vied 22, 310–318 (1972)

    MathSciNet  MATH  Google Scholar 

  13. Schönberger, T.: Ein Beweis des Petersenschen Graphensatzes. Acta Sci. Math. Szeged 7, 51–57 (1934)

    MATH  Google Scholar 

  14. Tutte, W.T.: The factors of graphs. Can. J. Math. 4, 314–328 (1952)

    MathSciNet  MATH  Google Scholar 

  15. Tutte, W.T.: A short proof of the factor theorem for finite graphs. Can. J. Math. 6, 347–352 (1954)

    MathSciNet  MATH  Google Scholar 

  16. Xiao, L., Liu, Y.: Even regular factor of regular graphs and number of cut edges. Southeast Asian Bull. Math. 31, 1019–1026 (2007)

    MathSciNet  MATH  Google Scholar 

Download references

Funding

Alexandr V. Kostochka: Research supported by National Science Foundation grant DMS1600592 and grants 18-01-00353A and 19-01-00682 of the Russian Foundation for Basic Research. Douglas B. West: Research supported by National Natural Science Foundation of China grants NSFC 11871439 and 11971429. Dara Zirlin: Research supported by Arnold O. Beckman Campus Research Board Award RB20003 of the University of Illinois at Urbana-Champaign.

Author information

Authors and Affiliations

  1. University of Illinois at Urbana-Champaign, Urbana, IL, 61801, USA

    Alexandr V. Kostochka, Douglas B. West & Dara Zirlin

  2. Sobolev Institute of Mathematics, Novosibirsk, 630090, Russia

    Alexandr V. Kostochka

  3. Université de Bordeaux, LaBRI UMR 5800, 33400, Talence, France

    André Raspaud

  4. University of Southern Denmark, Odense, Denmark

    Bjarne Toft

  5. Zhejiang Normal University, Jinhua, 321004, China

    Douglas B. West

Authors
  1. Alexandr V. Kostochka
    View author publications

    You can also search for this author inPubMed Google Scholar

  2. André Raspaud
    View author publications

    You can also search for this author inPubMed Google Scholar

  3. Bjarne Toft
    View author publications

    You can also search for this author inPubMed Google Scholar

  4. Douglas B. West
    View author publications

    You can also search for this author inPubMed Google Scholar

  5. Dara Zirlin
    View author publications

    You can also search for this author inPubMed Google Scholar

Corresponding author

Correspondence to Douglas B. West.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Kostochka, A.V., Raspaud, A., Toft, B. et al. Cut-Edges and Regular Factors in Regular Graphs of Odd Degree. Graphs and Combinatorics 37, 199–207 (2021). https://doi.org/10.1007/s00373-020-02242-0

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00373-020-02242-0

Keywords

Mathematics Subject Classification