Edge-connectivity and pairwise disjoint perfect matchings in regular graphs

DOI10.1007/S00493-023-00078-9MaRDI QIDQ6506498arXivFDO

Authors Yulai Ma, Davide Mattiolo, Eckhard Steffen, Isaak H. Wolf

Abstract: For $0leqtleqr$ 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)leqr-2$ for all $tot=5$, and $m(t,r)leqr-3$ if $r$ is even. We prove that $m(2l,r)leq3l-6$ for every $lgeq3$ and $rgeq2l$.

This page was built for publication: Edge-connectivity and pairwise disjoint perfect matchings in regular graphs

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