Article ID Journal Published Year Pages File Type
6423503 Discrete Mathematics 2011 5 Pages PDF
Abstract

The first result states that every 4-connected graph G with minimum degree δ and connectivity κ either contains a cycle of length at least 4δ−κ−4 or every longest cycle in G is a dominating cycle. The second result states that any such graph under the additional condition δ≥α either contains a cycle of length at least 4δ−κ−4 or is hamiltonian, where α denotes the independence number of G. Both results are sharp in all respects.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,