# Disjoint chorded cycles in graphs (2012)

Originators: Ron Gould, Paul Horn, Colton Magnant (presented by Paul Horn - REGS 2012)

Definitions: A chorded cycle in a graph $G$ is a subgraph consisting of cycle and an additional edge joining two vertices of the cycle, called a chord. A $k$-chorded cycle is a cycle with $k$ chords. A complete graph is an example of a cycle with many chords. Let $f(k)$ denote the number of chords of a spanning cycle in the complete graph $K_{k+1}$; note that $f(k)=\frac{(k+1)(k-2)}{2}$. Let $\delta(G)$ denote the mimimum degree of $G$ and $\bar{d}(G)$ denoted the average degree of $G$.

Background: Many authors have sought conditions for the existence of $t$ disjoint cycles or chorded cycles in a graph, where disjoint means sharing no vertices (or edges). Notable among these is the result of Corrádi-Hajnal [CH]: If $\delta(G) \geq 2t$ and $|V(G)| \geq 3t$, then $G$ contains $t$ vertex disjoint cycles. When $|V(G)|=3t$, this guarantees that $V(G)$ can be covered by vertex disjoint triangles.

Analogously, Finkel [F] showed that if $\delta(G) \geq 3t$ and $|V(G)| \geq 4t$, then $G$ contains $t$ disjoint chorded cycles. Note that every cycle has at least three vertices, and every chorded cycle has at least four vertices.

The Hajnal-Szemerédi Theorem [HS] extends the tight end of the Corrádi-Hajnal Theorem. It states that if $\delta(G) \geq kt$ and $|V(G)| = (k+1)t$, then $V(G)$ can be covered by $t$ disjoint copies of $K_{k+1}$. Each such subgraph can be viewed as an $f(k)$-chorded cycle, which suggests a conjecture.

Conjecture 1: (Gould-Horn-Magnant [GHM]) If $\delta(G) \geq kt$ and $|V(G)| \geq (k+1)t$, then $G$ contains $t$ vertex disjoint $f(k)$-chorded cycles.

Comments: For $t=1$, Ali-Staton [AS] showed that $G$ contains a $\lceil \frac{k(k-2)}{2} \rceil$-chorded cycle when $\delta(G) \geq k$. Their method was improved in [GHM] to show that $G$ contains an $f(k)$-chorded cycle when $\delta(G) \geq k$. Also, [GHM] obtains a weaker version of the conjecture: for sufficiently large $k$ and $t$, if $\delta(G) \geq kt$ and $|V(G)|$ is sufficiently large (for fixed $k$ and $t$), then $G$ contains $t$ disjoint $f(k)$-chorded cycles. To prove Conjecture 1, it remains to lower the constaint that $|V(G)|$ is "sufficiently large" to the desired constraint $|V(G)| \geq (k+1)t$. Additional related questions are due to Horn:

Question 2: When $G$ has no $f(k)$-chorded cycle, does it follow that $G$ has at least as many vertices with degree less than $k$ as it has vertices with degree at least $2k-1$?

Question 3: The harmonic average degree of $G$, denoted $\hat{d}(G)$, equals $\frac{n}{\sum_{v \in G} \frac{1}{\deg(G)}}$. Does $\hat{d}(G) \geq k+1$ imply that $G$ contains an $f(k)$-chorded cycle?

Comments: A key step of the proof in [GHM] is to establish that if $\bar{d}(G) \geq 2\sqrt{\frac{k(k-1)}{2}}$, then $G$ contains a $f(k)$-chorded cycle. A positive answer to Question 2 or Question 3 would allow this to be replaced with a more useful condition.

Definition: Chords of a cycle are crossing if their endpoints occur alternately along the cycle; that is, when the vertices of the cycle are placed on a circle and the chords are drawn as line segments, they cross.

Problem 4: Determine conditions guaranteeing the existence of a chorded cycle with $k$ pairs of crossing chords. Does $\delta(G) \geq k$ imply that $G$ contains a cycle with as many pairs of crossing chords as the complete graph $K_{k+1}$?

Remark: The number of pairs of crossing chords in $K_{k+1}$ is not the same as the crossing number of $K_{k+1}$.

References:
[AS] A. Ali, W. Staton, The Extremal Question for Cycles with Chords, Ars combinatoria, 51 (1999), 193-197.
[CH] K. Corrádi, A. Hajnal, On the number of independent circuits in a graph, Acta Math. Acad. Sci Hungar 14 (1963) 423-443.
[F] D. Finkel, On the number of independent chorded cycles in a graph, Discrete Mathematics, 22 (2008), 5265-5268.
[GHM] R. Gould, P. Horn, C. Magnant, Multiply chorded cycles, preprint (2012+)
[HS] A. Hajnal, E. Szemerédi, Proof of a Conjecture of Erdős." In Combinatorial Theory and Its Applications, Vol. 2 (Ed. P. Erdős, A. Rényi, and V. T. Sós) (North-Holland, 1970), 601-623.