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

Alexandr V. Kostochka, André Raspaud, Bjarne Toft, Douglas B. West, Dara Zirlin

Research output: Contribution to journalArticlepeer-review

Abstract

We study 2k-factors in (2 r+ 1) -regular graphs. Hanson, Loten, and Toft proved that every (2 r+ 1) -regular graph with at most 2r cut-edges has a 2-factor. We generalize their result by proving for k≤ (2 r+ 1) / 3 that every (2 r+ 1) -regular graph with at most 2 r- 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 2 r- 3 (k- 1) + 1 cut-edges but no 2k-factor. For k> (2 r+ 1) / 3 , there are graphs without cut-edges that have no 2k-factor, as studied by Bollobás, Saito, and Wormald.

Original languageEnglish (US)
Pages (from-to)199-207
Number of pages9
JournalGraphs and Combinatorics
Volume37
Issue number1
DOIs
StatePublished - Jan 2021

Keywords

  • Cut-edge
  • Graph factor
  • Matching
  • Regular graph

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Fingerprint

Dive into the research topics of 'Cut-Edges and Regular Factors in Regular Graphs of Odd Degree'. Together they form a unique fingerprint.

Cite this