Edge-Connectivity and Pairwise Disjoint Perfect Matchings in Regular Graphs

• DOI: 10.1007/s00493-023-00078-9
• Publication Date: 2023-12-19T17:02:22Z
• Authors: Yulai Ma; Davide Mattiolo; Eckhard Steffen; Isaak H. Wolf
• Keywords: Perfect matchings; Science & Technology; r-Graphs; Edge-colorings; 01 natural sciences; Regular graphs; Factors; Class 2 graphs; Physical Sciences; FOS: Mathematics; Mathematics - Combinatorics; Class 2 graphs; Edge-colorings; Factors; Perfect matchings; r-Graphs; Regular graphs; Combinatorics (math.CO); 0101 mathematics; Mathematics

AbstractFor $$0 \le t \le r$$

0 ≤ t ≤ 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$$

m ( 3 , 3 ) = m ( 4 , r ) = 1

, and $$m(t,r) \le r-2$$

m ( t , r ) ≤ r - 2

for all $$t \not = 5$$

t ≠ 5

, and $$m(t,r) \le r-3$$

m ( t , r ) ≤ r - 3

if r is even. We prove that $$m(2l,r) \le 3l - 6$$

m ( 2 l , r ) ≤ 3 l - 6

for every $$l \ge 3$$

l ≥ 3

and $$r \ge 2 l$$

r ≥ 2 l

.