Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4648357 | Discrete Mathematics | 2009 | 5 Pages |
Abstract
For a graph GG, p(G)p(G) and c(G)c(G) denote the orders of a longest path and a longest cycle of GG, respectively. For a graph GG, we denote by dG(x)dG(x) and κ(G)κ(G) the degree of a vertex xx in GG and the connectivity of GG, respectively. In this paper, we prove that if GG is a 3-connected graph of order nn such that ∑i=14dG(xi)≥n+κ(G)+3 for every independent set {x1,x2,x3,x4}{x1,x2,x3,x4}, then p(G)−c(G)≤1p(G)−c(G)≤1. This is a stronger result than the problem of Lu et al. [M. Lu, H. Liu, F. Tian, Two sufficient conditions for dominating cycles, J. Graph Theory 49 (2005) 134–150], and this degree condition is sharp.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Tomoki Yamashita,