On covering cubic graphs with three perfect matchings
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911460586684416 |
|---|---|
| author | Máčajová, Edita Mazák, Ján |
| author_facet | Máčajová, Edita Mazák, Ján |
| contents | For a bridgeless cubic graph $G$, $m_3(G)$ is the ratio of the maximum number of edges of $G$ covered by the union of $3$ perfect matchings to $|E(G)|$. We prove that for any $r\in [4/5, 1)$, there exist infinitely many cubic graphs $G$ such that $m_3(G) = r$. For any $r\in [9/10, 1)$, there exist infinitely many cyclically $4$-connected cubic graphs $G$ with $m_3(G) = r$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_05501 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On covering cubic graphs with three perfect matchings Máčajová, Edita Mazák, Ján Combinatorics Discrete Mathematics 05C70 For a bridgeless cubic graph $G$, $m_3(G)$ is the ratio of the maximum number of edges of $G$ covered by the union of $3$ perfect matchings to $|E(G)|$. We prove that for any $r\in [4/5, 1)$, there exist infinitely many cubic graphs $G$ such that $m_3(G) = r$. For any $r\in [9/10, 1)$, there exist infinitely many cyclically $4$-connected cubic graphs $G$ with $m_3(G) = r$. |
| title | On covering cubic graphs with three perfect matchings |
| topic | Combinatorics Discrete Mathematics 05C70 |
| url | https://arxiv.org/abs/2509.05501 |