The $K_{1,2}$-structure-connectivity of graphs

Abstract

In this paper, we mainly investigate $K_{1,2}$-structure-connectivity for any connected graph. Let $G$ be a connected graph with $n$ vertices, we show that $\kappa (G;K_{1,2})$ is well-defined if $diam(G)\ge 4$, or $n\equiv 1(\mathrm{mod}3)$, or $G\notin \{C_5,K_n\}$ when $n\equiv 2(\mathrm{mod}3)$, or there exist three vertices $u,v,w$ such that $N_G(u)\cap (N_G(v,w)\cup \{v,w\})=\varnothing$ when $n\equiv 0(\mathrm{mod}3)$. Furthermore, if $G$ has $K_{1,2}$-structure-cut, we prove $\kappa (G)/3\le \kappa (G;K_{1,2})\le \kappa (G)$.

18 pages,15 figures