Super $3$-Restricted Edge Connectivity of Triangle-Free Graphs

Abstract

Let $G=(V,E)$ be a connected graph. An edge set $S\subset E$ is a $k$-restricted edge cut if $G–S$ is disconnected and every component of $G–S$ has at least $k$ vertices. The $k$-restricted edge connectivity ${\lambda }_k(G)$ of $G$ is the cardinality of a minimum $k$-restricted edge cut of $G$. A graph $G$ is ${\lambda }_k$-connected if $k$-restricted edge cuts exist. A graph $G$ is called ${\lambda }_k$-optimal if ${\lambda }_k(G)={\xi }_k(G)$, where $${\xi }_k(G)=min\{|[X,Y]|:X\subseteq V,|X|=k\text{ and }G[X]\text{ is connected}\};$$ Here, $G[X]$ is the subgraph of $G\$$ induced by the vertex subset $X\subseteq V$, and $Y=V\setminus X$ is the complement of $X$; $[X,Y]$ is the set of edges with one end in $X$ and the other in $Y$. $G$ is said to be super-${\lambda }_k$ if each minimum $k$-restricted edge cut isolates a connected subgraph of order $k$. In this paper, we give some sufficient conditions for triangle-free graphs to be super-${\lambda }_3$.