Partitioning a graph into cycles with a specified number of chords

Abstract

For a graph $G$, let ${\sigma }_2(G)$ be the minimum degree sum of two non-adjacent vertices in $G$. A chord of a cycle in a graph $G$ is an edge of $G$ joining two non-consecutive vertices of the cycle. In this paper, we prove the following result, which is an extension of a result of Brandt et al. (J. Graph Theory 24 (1997) 165-173) for large graphs: For positive integers $k$ and $c$, there exists an integer $f(k,c)$ such that, if $G$ is a graph of order $n\ge f(k,c)$ and ${\sigma }_2(G)\ge n$, then $G$ can be partitioned into $k$ vertex-disjoint cycles, each of which has at least $c$ chords.

13 pages, 2 figures