Edge-connectivity and pairwise disjoint perfect matchings in regular graphs

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\ne 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 2l$.

12 pages, 7 figures

References in corpus (1)

• Pairwise disjoint perfect matchings in $r$-edge-connected $r$-regular graphs