Partitioning a graph into cycles with a specified number of chords

2018/08/12 by Chiba, Shuya, Jiang, Suyun, Yan, Jin
#05C38 #05C45 #05C70 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1808.03893

Abstract

For a graph G, let σ₂(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 ≥ f(k, c) and σ₂(G) ≥ n, then G can be partitioned into k vertex-disjoint cycles, each of which has at least c chords.

Related

• On Degree Sum Conditions and Vertex-Disjoint Chorded Cycles
• Disjoint chorded cycles in a 2-connected graph
• Partitioning a graph into a cycle and a sparse graph
• Spectral condition for the existence of a chorded cycle
• A refinement of theorems on vertex-disjoint chorded cycles