Expanding vertices to triangles in cubic graphs
Preprint
Abstract
Contraction of triangles is a standard operation in the study of cubic graphs, as it reduces the order of the graph while typically preserving many of its properties. In this paper, we investigate the converse problem, wherein certain vertices of cubic graphs are expanded into triangles to achieve a desired property. We first focus on bridgeless cubic graphs and define the parameter $T(G)$ as the minimum number of vertices that need to be expanded into triangles so that the resulting cubic graph can be covered with four perfect matchings. We relate this parameter to the concept of shortest cycle cover. Furthermore, we show that if $5$-Cycle Double Cover Conejcture holds true, then $T(G)\leq \frac{2}{5} |V(G)|$. We conjecture a tighter bound, $T(G)\leq \frac{1}{10}|V(G)|$, which is optimal for the Petersen graph, and show that this bound follows from major conjectures like the Petersen Coloring Conjecture. In the second part of the paper, we introduce the parameter $t(G)$ as the minimum number of vertex expansions needed for the graph to admit a perfect matching. We prove a Gallai type identity: $t(G)+\ell(G)=|V(G)|$, where $\ell(G)$ is the number of edges in a largest even subgraph of $G$. Then we prove the general upper bound $t(G)< \frac{1}{4}|V(G)|$ for cubic graphs, and $t(G)< \frac{1}{6}|V(G)|$ for cubic graphs without parallel edges. We provide examples showing that these bounds are asymptotically tight. The paper concludes with a discussion of the computational complexity of determining these parameters.
Keywords
All Related Versions
This publication has 16 references indexed in Scilit:
- Sets of r-Graphs that Color All r-GraphsCombinatorica, 2025
- On Perfect Matching Coverings and Even Subgraph CoveringsJournal of Graph Theory, 2015
- On disjoint matchings in cubic graphs: Maximum 2-edge-colorable and maximum 3-edge-colorable subgraphsDiscrete Applied Mathematics, 2014
- 1‐Factor and Cycle Covers of Cubic GraphsJournal of Graph Theory, 2014
- On Cubic Bridgeless Graphs Whose Edge-Set Cannot be Covered by Four Perfect MatchingsJournal of Graph Theory, 2013
- The equivalence of two conjectures of Berge and FulkersonJournal of Graph Theory, 2010
- Short cycle covers and the cycle double cover conjectureJournal of Combinatorial Theory, Series B, 1992
- Flows and generalized coloring theorems in graphsJournal of Combinatorial Theory, Series B, 1979
- Matching, Euler tours and the Chinese postmanMathematical Programming, 1973
- Blocking and anti-blocking pairs of polyhedraMathematical Programming, 1971