Cut-edges and regular factors in regular graphs of odd degree

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

*Kontaktforfatter for dette arbejde

Publikation: Bidrag til tidsskriftTidsskriftartikelForskningpeer review

Abstrakt

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≤(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.
OriginalsprogEngelsk
TidsskriftGraphs and Combinatorics
Vol/bind37
Sider (fra-til)199–207
ISSN0911-0119
DOI
StatusUdgivet - 2021

Bibliografisk note

9 pages

Emneord

  • math.CO

Fingeraftryk Dyk ned i forskningsemnerne om 'Cut-edges and regular factors in regular graphs of odd degree'. Sammen danner de et unikt fingeraftryk.

Citationsformater