05124996

j

05124996 Lin, Cheng-Kuan Huang, Hua-Min Hsu, Lih-Hsing On the spanning connectivity of graphs. Discrete Math. 307, No. 2, 285-289 (2007). 2007 Elsevier Science B.V. (North-Holland), Amsterdam EN spanning connectivity Hamiltonian Dirac theorem

doi:10.1016/j.disc.2006.06.021

Summary: A $k$-container $C(u,v)$ of $G$ between $u$ and $v$ is a set of $k$ internally disjoint paths between $u$ and $v$. A $k$-container $C(u,v)$ of $G$ is a $k^\ast$-container if it contains all vertices of $G$. A graph $G$ is $k^\ast$-connected if there exists a $k^\ast$-container between any two distinct vertices. The spanning connectivity of $G$, $\kappa^\ast(G)$, is defined to be the largest integer $k$ such that $G$ is $w^\ast$-connected for all $1\leq w\leq k$ if $G$ is a $1^\ast$-connected graph. In this paper, we prove that $\kappa^\ast(G)\geq 2\delta(G)-n(G)+2$ if $(n(G)/2)+1\leq\delta(G)\leq n(G)-2$. Furthermore, we prove that $\kappa^\ast(G\setminus T)\geq 2\delta(G)-n(G)+2-|T|$ if $T$ is a vertex subset with $|T|\leq 2\delta(G)-n(G)-1$.