Journal of Combinatorics
Volume 4 (2013)
Independent cycles and chorded cycles in graphs
Pages: 105 – 122
In this paper, we investigate sufficient conditions on the neighborhood of independent vertices which imply that a graph contains $k$ independent cycles or chorded cycles. This is related to several results of Corrádi and Hajnal, Justesen, Wang, and Faudree and Gould on graphs containing k independent cycles, and Finkel on graphs containing $k$ chorded cycles. In particular, we establish that if independent vertices in $G$ have neighborhood union at least $2k + 1$, then $G$ has $k$ chorded cycles, so long as $|G| > 30k$, and settling a conjecture of and improving a result of Faudree and Gould, who establish that 3k suffices. Additionally, we show that a graph with neighborhood union of independent vertices at least $4k + 1$ has at least $k$ chorded cycles; Finkel previously established that minimum degree $3k$ was also a sufficient condition for this.
Published 16 May 2013