Degree conditions and cycle extendability
type: Item
instance of: scholarly article
title: Degree conditions and cycle extendability
zbMATH Open document ID: 0839.05058
DOI: 10.1016/0012-365X(93)E0193-8
published in: Discrete Mathematics
publication date: 1996-06-05T00:00:00Z
review text: 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\).
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 778529
zbMATH Keywords: cycle extendability
zbMATH Keywords: minimum degree
author: Ralph Faudree
author: Ronald Gould
author: Michael Jacobson
author: Linda Lesniak
reviewed by: Jørgen Bang-Jensen
MaRDI profile type: Publication
cites work: Some Theorems on Abstract Graphs
cites work: Extending cycles in directed graphs
cites work: Extending cycles in graphs
full work available at URL: 0012-365x(93)e0193-8
OpenAlex ID: W2053969447
description: scientific article; zbMATH DE number 778529