Cycles containing many vertices of large degree
type: Item
instance of: scholarly article
title: Cycles containing many vertices of large degree
zbMATH Open document ID: 0768.05066
DOI: 10.1016/0012-365X(92)90612-J
published in: Discrete Mathematics
publication date: 1993-01-16T00:00:00Z
review text: This paper extends two results regarding lengths of cycles containing vertices of large degree in 2-connected graphs. The author improves Shi Ronghua's extension of Dirac's condition for hamiltonicity by using his procedure to show: If \(G\) is a 2-connected graph on \(n\) vertices and \(r\) is a real number, then \(G\) has a cycle missing at most \(\max\{0,n-2r\}\) vertices of those with degree at least \(r\). He then betters this result by showing: If \(G\) is a 2-connected graph on \(n\) vertices and \(r\) is a real number such that \(r\geq (n+2)/3\), then \(G\) contains a cycle which either contains all vertices of degree at least \(r\) or is at least \(2r\) in length. This theorem which extends a result of Häggkvist and Jackson is best possible in two senses: (1) \(G\) can be given so that no cycle contains all the vertices of degree at least \(r\) and every cycle of \(G\) has length at most \(2r\), and (2) the bound \((n+2)/3\) cannot be relaxed.
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 89912
zbMATH Keywords: dominating cycles
zbMATH Keywords: long cycles
author: Henk Jan Veldman
reviewed by: Norman F. Quimpo
MaRDI profile type: Publication
cites work: Q5422499
cites work: Some Theorems on Abstract Graphs
cites work: Q3691770
cites work: Q3880849
cites work: Q5628163
cites work: Existence of dominating cycles and paths
full work available at URL: 0012-365x(92)90612-j
OpenAlex ID: W2163667514
Wikidata QID: Q127847433
description: scientific article; zbMATH DE number 89912