Induced Cycles in Graphs

Abstract

The maximum cardinality of an induced $2$-regular subgraph of a graph $G$ is denoted by $c_{\mathrm{ind}}(G)$. We prove that if $G$ is an $r$-regular graph of order $n$, then $c_{\mathrm{ind}}(G)\ge \frac{n}{2(r-1)}+\frac{1}{(r-1)(r-2)}$ and we prove that if $G$ is a cubic claw-free graph on order $n$, then $c_{\mathrm{ind}}(G)>13n/20$ and this bound is asymptotically best possible.

17 pages

Cited by in corpus (1)

• Induced 2-Regular Subgraphs in k-Chordal Cubic Graphs