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.