On covering cubic graphs with 3 perfect matchings
By: Edita Máčajová, Ján Mazák
Potential Business Impact:
Finds ways to connect points in networks.
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$.
Similar Papers
On the time complexity of finding a well-spread perfect matching in bridgeless cubic graphs
Data Structures and Algorithms
Finds special paths in tricky networks faster.
Expanding vertices to triangles in cubic graphs
Combinatorics
Makes complex network puzzles easier to solve.
Graphs With the Same Edge Count in Each Neighborhood
Combinatorics
Finds rules for making special connection patterns.