A Note on Dominating Cycles in Tough Graphs

Abstract

A cycle \(C\) in a graph \(G\) is said to be a dominating cycle if every vertex of \(G\) has a neighbor on \(C\). Strengthening a result of Bondy and Fan [3] for tough graphs, we prove that a \(k\)-connected graph \(G\) (\(k \geq 2\)) of order \(p\) with \(t(G) > \frac{k}{k+1}\) has a dominating cycle if \(\sum_{x \in S} \geq p – 2k – 2\) for each \(S \subset V(G)\) of order \(k+1\) in which every pair of vertices in \(S\) have distance at least four in \(G\).