The Edge-Connectivity of Strongly 3-Walk-Regular Graphs

E.R. van Dam and G.R. Omidi generalized the concept of strongly regular graphs as follows. If for any two vertices the number of \(\ell \)-walks (walks of length \(\ell \)) from one vertex to the other is the same which depends only on whether the two vertices are the same, adjacent or non-adjacent, then G is called a strongly \(\ell \)-walk-regular graph. The existence of strongly \(\ell \)-walk-regular graphs which are not strongly 3-walk-regular graphs is unknown. In this paper, we prove that the edge-connectivity of a connected strongly 3-walk-regular graph G of degree \(k\ge 3\) is equal to k. Moreover, if G is not the graph formed by adding a perfect matching between two copies of \(K_{4}\), then each edge cut set of size k is precisely the set of edges incident with a vertex of G. For a regular graph G in general, we also give a sufficient and tight condition such that G is 1-extendable.