On the maximally edge-connected square graphs with degree sequence conditions

Source abstract

Let $G=(V(G),E(G))$ be a finite connected simple graph. The edge-connectivity $λ(G)$ of $G$ is the minimum number of edges that must be removed to make $G$ disconnected. We call $G$ maximally edge-connected when $λ(G)=δ(G)$, where $δ(G)$ is the minimum degree of $G$. The square graph $G^2$ of $G$ is the graph with vertex set $V(G)$, where two distinct vertices $u$ and $v$ are adjacent in $G^2$ precisely when their distance in $G$ is at most two. In this paper, first we prove that if $λ(G)\geq4$ and $λ(G^2) λ(G)^{3/2}-\frac54λ(G)$, which extends the result in \cite{ChenXu} from the edge-connectivity range $4\leqλ(G)\leq7$ to $λ(G)\geq4$. Then we show that $G^2$ is maximally edge-connected if one of the following conditions hold: (i) $δ(G)\geq\lfloor(n+2)/4\rfloor$, or $δ(G)\leq\lfloor(n+2)/4\rfloor-1$ and $\sum_{i=1}^{2k}d_{n+1-i}\geq k(n-4)-2δ(G)+3$, where $k$ is an integer satisfying $2\leq k\leqδ(G)+2$ and $d_1\geq d_2\geq\cdots\geq d_n$ are the degrees of $G$; (ii) $d_{n-δ(G)}+d_n\geq(3n-9)/4$.