Edge-connectivity and pairwise disjoint perfect matchings in regular graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2022
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916149303705600 |
|---|---|
| author | Ma, Yulai Mattiolo, Davide Steffen, Eckhard Wolf, Isaak H. |
| author_facet | Ma, Yulai Mattiolo, Davide Steffen, Eckhard Wolf, Isaak H. |
| contents | For $0 \leq t \leq 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) \leq r-2$ for all $t \not = 5$, and $m(t,r) \leq r-3$ if $r$ is even. We prove that $m(2l,r) \leq 3l - 6$ for every $l \geq 3$ and $r \geq 2 l$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2208_14835 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Edge-connectivity and pairwise disjoint perfect matchings in regular graphs Ma, Yulai Mattiolo, Davide Steffen, Eckhard Wolf, Isaak H. Combinatorics For $0 \leq t \leq 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) \leq r-2$ for all $t \not = 5$, and $m(t,r) \leq r-3$ if $r$ is even. We prove that $m(2l,r) \leq 3l - 6$ for every $l \geq 3$ and $r \geq 2 l$. |
| title | Edge-connectivity and pairwise disjoint perfect matchings in regular graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2208.14835 |