Article ID Journal Published Year Pages File Type
4649917 Discrete Mathematics 2008 8 Pages PDF
Abstract

For a graph G  , let σk(G)σk(G) be the minimum degree sum of an independent set of k vertices. Ore showed that if G   is a graph of order n⩾3n⩾3 with σ2(G)⩾nσ2(G)⩾n then G   is hamiltonian. Let κ(G)κ(G) be the connectivity of a graph G. Bauer, Broersma, Li and Veldman proved that if G is a 2-connected graph on n   vertices with σ3(G)⩾n+κ(G)σ3(G)⩾n+κ(G), then G is hamiltonian. On the other hand, Bondy showed that if G is a 2-connected graph on n   vertices with σ3(G)⩾n+2σ3(G)⩾n+2, then each longest cycle of G is a dominating cycle. In this paper, we prove that if G is a 3-connected graph on n   vertices with σ4(G)⩾n+κ(G)+3σ4(G)⩾n+κ(G)+3, then G contains a longest cycle which is a dominating cycle.

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