Let S be a set of vertices of a k-connected graph G. We denote the smallest sum of degrees of k + 1 independent vertices of S by σk + 1(S; G). We obtain a sharp lower bound of σk + 1(S; G) for the vertices of S to be contained in a common cycle of G. This result gives a sufficient condition for a k-connected graph to be hamiltonian.
ASJC Scopus subject areas
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics