Journal of Combinatorics

Volume 4 (2013)

Number 1

Independent cycles and chorded cycles in graphs

Pages: 105 – 122

DOI: http://dx.doi.org/10.4310/JOC.2013.v4.n1.a6

Authors

Ronald J. Gould (Department of Mathematics and Computer Science, Emory University, Atlanta, Georgia, U.S.A.)

Kazuhide Hirohata (Department of Electronic and Computer Engineering, Ibaraki National College of Technology, Ibaraki, Japan)

Paul Horn (Department of Mathematics, Harvard University, Cambridge, Massachusetts, U.S.A.)

Abstract

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.

Full Text (PDF format)