Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4649917 | Discrete Mathematics | 2008 | 8 Pages |
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
Tomoki Yamashita,