A degree sum condition concerning the connectivity and the independence number of a graph (Q1014827): Difference between revisions

Let \(G\) be a graph \(S\subset V(G)\). We denote by \(\alpha(G)\) the maximum number of pairwise nonadjacent vertices in \(S\). For \(x,y\in V(G)\), the local connectivity \(k(x,y)\) is defined to be the maximum number of internally-disjoint path connecting \(x\) and \(y\) in \(G\). The authors define \(k(S)=\min\{k(x,y): x,y\in S, x\neq y\}\). If \(\alpha(S)\geq k\), let \(\sigma_k(S)= \min\{d_G(x)\) \(X\) is an independent set of \(S\) with \(|X|= k\}\); otherwise \(\sigma_k(S)= +\infty\), respectively. The authors proved the following theorem and showed that it is the best possible. Let \(G\) be a graph on \(n\) vertices, and \(S\subset V(G)\) with \(k(S)\geq 3\). If \(\sigma_4(S)\geq n+ k(S)+ \alpha(S)-1\), then \(S\) is cyclable in \(G\). The authors compare this result with previous ones and show that this degree condition is sharp and this gives a new degree sum condition for a three-connected graph to be Hamiltonian.