Cycles containing many vertices of large degree (Q1197038)

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.