Edge-Connectivity and Pairwise Disjoint Perfect Matchings in Regular Graphs
Open Access
- 19 December 2023
- journal article
- research article
- Published by Springer Nature in Combinatorica
- Vol. 44 (2) , 429-440
Abstract
For $$0 \le t \le r$$ let m(t, r) be the maximum number s such that every t-edge-connected r-graph has s pairwise disjoint perfect matchings. There are only a few values of m(t, r) known, for instance $$m(3,3)=m(4,r)=1$$ , and $$m(t,r) \le r-2$$ for all $$t \not = 5$$ , and $$m(t,r) \le r-3$$ if r is even. We prove that $$m(2l,r) \le 3l - 6$$ for every $$l \ge 3$$ and $$r \ge 2 l$$ .
Keywords
All Related Versions
Funding Information
- Universität Paderborn
This publication has 8 references indexed in Scilit:
- Pairwise Disjoint Perfect Matchings in r-Edge-Connected r-Regular GraphsSIAM Journal on Discrete Mathematics, 2023
- Highly edge‐connected regular graphs without large factorizable subgraphsJournal of Graph Theory, 2021
- Factorizing regular graphsJournal of Combinatorial Theory, Series B, 2020
- Indecomposabler-graphs and some other counterexamplesJournal of Graph Theory, 1999
- Indecomposable r‐graphs and some other counterexamplesJournal of Graph Theory, 1999
- Chromatic-index-critical graphs of even orderJournal of Graph Theory, 1999
- On Multi-Colourings of Cubic Graphs, and Conjectures of Fulkerson and TutteProceedings of the London Mathematical Society, 1979
- Regular n-valent n-connected nonHamiltonian non-n-edge-colorable graphsJournal of Combinatorial Theory, Series B, 1973