A Degree Sum Condition Concerning the Connectivity and the Independence Number of a Graph

摘要

Let G be a graph and S ? V(G). We denote by α(S) the maximum number of pairwise nonadjacent vertices in S. For x, y ∈ V(G), the local connectivity κ(x, y) is defined to be the maximum number of internally-disjoint paths connecting x and y in G. We define $kappa(S)=min{kappa(x,y) : x,y in S,xnot=y}$ . In this paper, we show that if κ(S) ≥ 3 and $sum_{i=1}^4 d_{G}{(x_i)} ge |V(G)|+kappa(S)+alpha (S)-1$ for every independent set {x 1, x 2, x 3, x 4} ? S, then G contains a cycle passing through S. This degree condition is sharp and this gives a new degree sum condition for a 3-connected graph to be hamiltonian.