On covering cubic graphs with three perfect matchings
Abstract
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$.
Fields of Study & Subjects
Advanced Graph Theory Research
Graph Labeling and Dimension Problems
graph theory and CDMA systems
Publication details
- Journal / source
- Discussiones Mathematicae Graph Theory
- Publication date
- 1 January 2026
- Language
- EN