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

#### Abstract

Let *n* be even, let π = (*d*_{1}, ... , *d _{n}*) be a graphic degree sequence, and let π -

*k*= (

*d*

_{1}-

*k*, ... ,

*d*-

_{n}*k*) also be graphic. Kundu proved that π has a realization

*G*containing a

*k*-factor, or

*k*-regular graph. Another way to state the conclusion of Kundu's theorem is that π potentially contains a

*k*-factor. Busch, Ferrara, Hartke, Jacobsen, Kaul, and West conjectured that more was true: π potentially contains

*k*edge-disjoint 1-factors. Along these lines, they proved π 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 π potentially has edge-disjoint copies of a (

*k*-4)-factor and four 1-factors. We also prove that π potentially has (⌊k/2⌋+2) edge-disjoint 1-factors, but in this case cannot prove the existence of a large regular graph.

#### Keywords

#### Full Text:

PDFDOI: http://dx.doi.org/10.5614/ejgta.2021.9.1.8

#### References

Arthur H. Busch, Michael J. Ferrara, Stephen G. Hartke, Michael S. Jacobson, Hemanshu Kaul, and Douglas B. West, Packing of graphic n-tuples, J. Graph Theory, 70(1):29--39, 2012. Preprint available at http://www.math.illinois.edu/~dwest/pubs/degpack.pdf.

Yong~Chuan Chen, A short proof of Kundu's k-factor theorem, Discrete Math., 71(2):177--179, 1988. Available at

http://www.sciencedirect.com/science/article/pii/0012365X88900702.

Kundu, The k-factor conjecture is true, Discrete Math., 6:367--376, 1973. Available at

http://www.sciencedirect.com/science/article/pii/0012365X7390068X.

Daniel Leven and Zvi Galil, NP completeness of finding the chromatic index of regular graphs, J. Algorithms, 4(1):35--44, 1983. Available at

http://www.sciencedirect.com/science/article/pii/0196677483900329.

Julius Petersen, Die Theorie der regularen graphs, Acta Math., 15(1):193--220, 1891.

Douglas B. West, Introduction to graph theory, Prentice Hall Inc., Upper Saddle River, NJ, 1996.

### Refbacks

- There are currently no refbacks.

ISSN: 2338-2287

This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.