On Super Restricted Edge-Connectivity of Vertex-Transitive Graphs

Abstract

Let $X=(V,E)$ be a connected vertex-transitive graph with degree $k$. Call $X$ super restricted edge-connected, in short, sup-${\lambda }^{\prime }$, if $F$ is a minimum edge set of $X$ such that $X–F$ is disconnected and every component of $X–F$ has at least two vertices, then $F$ is the set of edges adjacent to a certain edge in $X$. Wang [Y, Q, Wang, Super restricted edge-connectivity of vertex-transitive graphs, Discrete Mathematics $289(2004)199-205]$ proved that a connected vertex-transitive graph with degree $k>2$ and girth $g>4$ is sup-${\lambda }^{\prime }$. In this paper, by studying the $k$-superatom of $X$, we present sufficient and necessary conditions for connected vertex-transitive graphs and Cayley graphs with degree $k>2$ to be sup-${\lambda }^{\prime }$. In particular, sup-${\lambda }^{\prime }$ connected vertex-transitive graphs with degree $k>2$ and girth $g>3$ are completely characterized. These results can be seen as an improvement of the one obtained by Wang.