Multi-switch: a tool for finding potential edge-disjoint 1-factors

DOI10.5614/EJGTA.2021.9.1.8zbMATH Open1468.05039arXiv1508.00079OpenAlexW3158328385MaRDI QIDQ4958048FDOQ4958048

Authors: Tyler Seacrest 

Publication date: 6 September 2021

Published in: Electronic Journal of Graph Theory and Applications (Search for Journal in Brave)

Abstract: Let $n$ be even, let $pi=(d_1,ldots,d_n)$ be a graphic degree sequence, and let $pi-k=(d_1-k,ldots,d_n-k)$ also be graphic. Kundu proved that $pi$ has a realization $G$ containing a $k$-factor, or $k$-regular graph. Another way to state the conclusion of Kundu's theorem is that $pi$ emph{potentially} contains a $k$-factor. Busch, Ferrara, Hartke, Jacobsen, Kaul, and West conjectured that more was true: $pi$ potentially contains $k$ edge-disjoint $1$-factors. Along these lines, they proved $pi$ would potentially contain edge-disjoint copies of a $(k-2)$-factor and two $1$-factors. We follow the methods of Busch et al. but introduce a new tool which we call a multi-switch. Using this new idea, we prove that $pi$ potentially has edge-disjoint copies of a $(k-4)$-factor and four $1$-factors. We also prove that $pi$ potentially has ($lfloork/2floor+2$) edge-disjoint $1$-factors, but in this case cannot prove the existence of a large regular graph.

Full work available at URL: https://arxiv.org/abs/1508.00079

Recommendations

• A short proof of Kundu's k-factor theorem
• The existence of even regular factors of regular graphs on the number of cut edges
• Publication:3487420
• Degree sequences and the existence of \(k\)-factors
• \(k\) -factors in regular graphs

zbMATH Keywords

graphmatchingdegree sequenceKundu's theorem

Mathematics Subject Classification ID

Vertex degrees (05C07)

Cites Work

• Title not available (Why is that?)
• Packing of graphic \(n\)-tuples
• NP completeness of finding the chromatic index of regular graphs
• A short proof of Kundu's k-factor theorem
• The k-factor conjecture is true

Cited In (3)

• Maximally edge‐connected realizations and Kundu's k $k$‐factor theorem
• LegendreSobolev
• On a conjecture that strengthens Kundu's \(k\)-factor theorem

This page was built for publication: Multi-switch: a tool for finding potential edge-disjoint 1-factors

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4958048)