Score: 0

On covering cubic graphs with 3 perfect matchings

Published: September 5, 2025 | arXiv ID: 2509.05501v1

By: Edita Máčajová, Ján Mazák

Potential Business Impact:

Finds ways to connect points in networks.

Business Areas:
Table Tennis Sports

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$.

Country of Origin
🇸🇰 Slovakia

Page Count
8 pages

Category
Mathematics:
Combinatorics