Cycle Covers in Graphs Without Subdivisions of \(K_4\)

Hong-Jian Lai1, Hongyuan Lai2
1University of West Virginia, Morgantown, WV 26506
2Wayne State Univerity, Detroit, MI 48202

Abstract

In \([B]\), Bondy conjectured that if \(G\) is a \(2\)-edge-connected simple graph with \(n\) vertices, then \(G\) admits a cycle cover with at most \((2n-1)/{3}\) cycles. In this note, we show that if \(G\) is a \(2\)-edge-connected simple graph with \(n\) vertices and without subdivisions of \(K_4\), then \(G\) has a cycle cover with at most \((2n-2)/{3}\) cycles and we characterize all the extremal graphs. We also show that if \(G\) is \(2\)-edge-connected and has no subdivision of \(K_4\), then \(G\) is mod \((2k+1)\)-orientable for any integer \(k \geq 1\).