Cycles Through Specified Vertices in \(1\)-Tough Graphs

Ladislav Stacho 1
1Institute for Informatics, Slovak Academy of Sciences P.O.Box 56, 840 00 Bratislava 4, Slovakia

Abstract

Bollobás, Brightwell [1] and independently Shi [3] proved the existence of a cycle through all vertices of degree at least \(\frac{n}{2}\) in any \(2\)-connected graph of order \(n\). The aim of this paper is to show that the above degree requirement can be relaxed for \(1\)-tough graphs.