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’\), 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’\). 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’\). In particular, sup-\(\lambda’\) 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.