Degree conditions and cycle extendability (Q1894763): Difference between revisions

A cycle \(C\) in a graph \(G\) is extendable if \(G\) has a cycle \(C'\) such that \(V(C)\subset V(C')\) and \(|V(C)|= |V(C')|+ 1\). This definition is due to Hendry. A chord of a cycle is any edge between vertices in the cycle that is not in the cycle. In this paper the authors consider extendability of cycles where one requires most of the edges of the cycle \(C\) to remain edges in \(C'\). \(C\) is \(k\)-chord extendable if it is extendable to a cycle \(C'\) using at most \(k\) chords of \(C\). A graph \(G\) is \(k\)-chord extendable if each non-Hamiltonian cycle is \(k\)-chord extendable. The main results of the paper are: Let \(G\) be a graph of order \(n\geq 3\) and let \(\delta(G)\) denote the minimum degree of \(G\). Then (1) \(\delta(G)> 3n/4-1\) implies that \(G\) is 0-chord extendable; (2) \(\delta(G)> 5n/9\) implies that \(G\) is 1-chord extendable; (3) \(\delta(G)> \lfloor n/2\rfloor\) implies that \(G\) is 2-chord extendable. The authors also show that each of these results is sharp for infinitely many integers \(n\).