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\ge 2$) of order $p$ with $t(G)>\frac{k}{k+1}$ has a dominating cycle if $\sum _{x\in S}\ge 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$.