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

Abstract

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.

1 Introduction

All graphs considered in this paper are finite, undirected and simple. Let G be a graph. The vertex set and edge set of G are denoted by V(G) and E(G) respectively. Let B be a subset of the vertex set V(G) of G. The graph $G-B$ is derived from G by deleting the vertices of B and the edges incident with a vertex of B. If $B=\left\{ u\right\}$, we denote $G-B$ by $G-u$ for convenience. The graph G[B] is the subgraph of G induced by B. Let E be a subset of the edge set E(G). The graph $G-E$ is defined with vertex set $V(G-E)=V(G)$ and edge set $E(G)-E$. Let $S_{1}$ and $S_{2}$ be two disjoint subsets of V(G) (or two vertex-disjoint subgraphs of G). Denote the set of edges between $S_{1}$ and $S_{2}$ by $E(S_{1},S_{2})$. Let G be a connected graph. A subset S of V(G) is said to be a cut set if $G-S$ is not connected. The connectivity of a non-complete graph G is the minimum size of a cut set in G. We always admit that the connectivity of $K_{k+1}$ is k. A subset N of the edge set E(G) is said to be an edge cut set of G if there are two disjoint subsets A and B of V(G) such that $V(G)=A\bigcup B$ and $E(A,B)=N$. An edge cut set $N=E(A,B)$ is called a cyclic edge cut set if both G[A] and G[B] contain a cycle. The (cyclic) edge-connectivity of G is the minimum size of a (cyclic) edge cut set in G.

A matchingM of G is a subset of E(G) such that the edges are independent in G. If M covers each vertex of G, then M is called a perfect matching or a one-factor. The graph G is 1-extendable if each edge of G is contained in a perfect matching of G, and G is factor-critical if $G-u$ has a perfect matching for any vertex u of G. Tutte Theorem (see Theorem 2.4) is a fundamental result in matching theory, referring to [1, 14].

E.R. van Dam and G.R. Omidi generalized the concept of strongly regular graphs to strongly $\ell$-walk-regular graphs in [9]. For an integer $\ell \ge 2$, a (non-complete) graph G is called a strongly$\ell$-walk-regular graph, if for any two vertices of G the number of 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. In [9], it was shown that a strongly $\ell$-walk-regular graph, which is not a strongly regular graph, is either a strongly $\ell$-walk-regular graph for any odd integer $\ell \ge 3$, or a strongly $\ell$-walk-regular graph for a unique odd integer $\ell \ge 3$. There are many examples of strongly 3-walk-regular graphs which are not strongly regular graphs. However, the existence of strongly $\ell$-walk-regular graphs which are not strongly 3-walk-regular graphs is unknown.

Let $1,2,\ldots$, and $v=|V(G)|$ be the vertices of G. The adjacency matrix of G is a square matrix of order |V(G)|, which is denoted by $A=(a_{ij})$, where $a_{ij}=1$ if the vertex i and the vertex j are adjacent, and $a_{ij}=0$ otherwise. The eigenvalues of G are the eigenvalues of A. In the sense of adjacency matrix, G is a strongly regular graph if there exist three numbers k, a and b such that $A^{2}=kI+aA+b(J-I-A)$, where I is the identity matrix and J is the all-one matrix. Similarly, for an integer $\ell \ge 2$, a graph G is called a strongly $\ell$-walk-regular graph if $A^{\ell }=aI+bA+c(J-I-A)$ for some numbers a, b and c. It is obvious that a strongly regular graph is also a strongly $\ell$-walk-regular graph for any integer $\ell \ge 2$ by induction on $\ell$ as $A^{2}$ is a linear combination of A, I and J.

In general, a strongly $\ell$-walk-regular graph can be not regular, and can be connected even for $c=0$. It determined the strongly $\ell$-walk-regular graphs with $c=0$ in Proposition 5.1 from [9]. These graphs are precisely either a disjoint union of complete graphs of the same order, or a disjoint union of complete bipartite graphs of the same size and possibly some isolated vertices when $\ell$ is odd. If $c>0$, then J can be expressed as a polynomial of A and thus $AJ=JA$, which implies that G is regular. Moreover, since for any two non-adjacent vertices there is a walk of length $\ell$ connecting them when $c>0$, the diameter of G is at most $\ell$, and thus G is connected.

Let G be a connected strongly regular graph of degree $k\ge 3$. In [3] it was shown that the connectivity of G is equal to k, and each cut set of size k is precisely the set of neighbours of a vertex in G. Later, the minimum size of the cut sets which disconnect G into non-singleton components was partially studied in [4, 5]. For the cyclic edge-connectivity of G, it was studied in [15].

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}$, which has parameters $v=8,k=4,a=6,b=10$ and $c=6$, 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. Our proofs are mainly based on spectrum technique and Tutte Theorem (see Theorem 2.4). In this paper, for any terminology used but not defined, one may refer to [11, 13].

2 Main Tools

For a connected k-regular graph with four distinct eigenvalues, a characterization of the spectrum is given in [6, Theorem 2.6]. The characterization is as follows.

Lemma 2.1

Let G be a connected k-regular graph on v vertices with eigenvalues with multiplicities $k^{1}, \theta _{1}^{m_{1}}, \theta _{2}^{m_{2}}$ and $\theta _{3}^{m_{3}}$, and let $m =\frac{v-1}{3}$. Then $m_{1} = m_{2} = m_{3} = m$ and $k = m$ or $k = 2m$, or G has two or four integral eigenvalues. Moreover, if G has exactly two integral eigenvalues, then the other two have the same multiplicities and are of the form $\frac{p\pm \sqrt{q}}{2}$, where p, q are integers.

The following conclusion is from Lemma 3.3 and Proposition 4.1 in [9].

Lemma 2.2

Let G be a connected strongly 3-walk-regular graph which is not a strongly regular graph. Then G has four distinct eigenvalues $k> \theta _{1}> \theta _{2} > \theta _{3}$ and $\theta _{1}+\theta _{2}+\theta _{3}=0$, where k is the degree of G.

The following conclusion is a result based on interlacing technique, referring to Corollary 4.8.4 in [2].

Lemma 2.3

Let G be a connected k-regular graph on v vertices. Suppose that S is a subset of V(G). Then $|E(S,\overline{S})|\ge \frac{(k-\theta )|S|(v-|S|)}{v}$, where $\theta$ is the second largest eigenvalue of G and $\overline{S}=V(G)-S$.

Let G be a graph and S be a subset of V(G). The number of odd components of $G-S$ is denoted by $o(G-S)$. Tutte [14] (or [1]) proved the following conclusion.

Theorem 2.4

A graph G has a perfect matching if and only if for any subset S of V(G), it satisfies that $o(G-S)\le |S|$.

3 Main Results

Let G be a strongly regular graph of degree $k\ge 3$. Since the edge-connectivity of a graph is not less than its connectivity, thus we have that the edge-connectivity of G is equal to k by the result of [3], and each edge cut set of size k is precisely the set of edges incident with a vertex in G as any two non-adjacent vertices of G has a common neighbour. (This conclusion can be also derived directly from the result in [15].)

Note 1

Let G be a connected strongly 3-walk-regular graph on v vertices of degree $k\ge 3$. We can suppose that G is not a strongly regular graph by the above discussion when we study the edge-connectivity of G. Thus by Lemma 2.2, G has four distinct eigenvalues and the spectrum can be denoted by $k^{1}, \theta _{1}^{m_{1}}, \theta _{2}^{m_{2}}$ and $\theta _{3}^{m_{3}}$. Let A be the adjacency matrix of G. We can suppose that $A^{3}=aI+bA+c(J-I-A)$ for some numbers (integers) a, b and c. Since there are precisely a 3-walks from each vertex to itself, thus each vertex is in $\frac{a}{2}$ triangles. Since for any two adjacent vertices there are precisely b 3-walks from one vertex to the other, thus each edge is in $b-2k+1$ 4-cycles in G. In the following discussions on strongly 3-walk-regular graphs, we always have this assumption.

Theorem 3.1

Let G be a connected strongly 3-walk-regular graph defined as Note 1. If G has non-integral eigenvalues, then the spectrum is $k^{1}, \left( \frac{m+\sqrt{n}}{2}\right) ^{f}, (-m)^{g},$$\left( \frac{m-\sqrt{n}}{2}\right) ^{f}$, where $m, n \in Z$, $m\ne 0$, $f=\frac{v-1-\frac{k}{m}}{3}$ and $g=\frac{v-1+\frac{2k}{m}}{3}$. Moreover, we have the following conclusions.

• (i) For $m=1$, then $k\ge 8$ is even, and the four distinct eigenvalues of G are $k, -1$ and $\frac{1\pm \sqrt{6k-3}}{2}$. Moreover, we have $a-c=\frac{3k-2}{2}, b-c=\frac{3k}{2}$ and $2cv=(k+1)(k-2)(2k-1)$.

• (ii) For $m\ne 1$, if $k\ge 3$ is odd, then $\lambda _{2}(G)\le \frac{\sqrt{18k-6}}{3}$; if $k\ge 4$ is even, then $\lambda _{2}(G)\le \frac{\sqrt{18k-12}}{3}$.

• (iii) We must have $k\ne 3$ and $k\ne 4$, which means that if G has non-integral eigenvalues, then $k\ge 5$.

Proof

By Lemma 2.2, we have $\theta _{1}+\theta _{2}+\theta _{3}=0$. If $m_{1} = m_{2} = m_{3} = t$, then $0=tr(A)=k+t(\theta _{1}+\theta _{2}+\theta _{3})=k$, a contradiction. Therefore, G has precisely two distinct non-integral eigenvalues by Lemma 2.1. Moreover, the two distinct non-integral eigenvalues have the same multiplicity and are of the form $\frac{m\pm \sqrt{n}}{2}$, with $m, n \in Z$. Then another eigenvalue is $-m$ as $\theta _{1}+\theta _{2}+\theta _{3}=0$. Now we can suppose that the eigenvalues with multiplicities are $k^{1}, \left( \frac{m+\sqrt{n}}{2}\right) ^{f}, (-m)^{g}, \left( \frac{m-\sqrt{n}}{2}\right) ^{f}$. If $m=0$, then $0=tr(A)=k+(f-g)m=k$, a contradiction. Now suppose $m\ne 0$. Combining $v=1+2f+g$ with $0=tr(A)=k+(f-g)m$, we have $f=\frac{v-1-\frac{k}{m}}{3}$ and $g=\frac{v-1+\frac{2k}{m}}{3}$.

Since all eigenvalues of A except k are the roots of equation $x^{3}+(c-b)x-(a-c)=0$, we have $(-m)^{3}+(c-b)(-m)-(a-c)=0$ (1),

$\left( \frac{m+\sqrt{n}}{2}\right) ^{3}+(c-b)\left( \frac{m+\sqrt{n}}{2}\right) -(a-c)=0$ (2)

and $\left( \frac{m-\sqrt{n}}{2}\right) ^{3}+(c-b)\left( \frac{m-\sqrt{n}}{2}\right) -(a-c)=0$ (3).

By equality (1) we have $m^{3}=(b-c)m-(a-c)$ (4).

By (2)–(3) we have $3m^{2}+n=4(b-c)$ (5).

By (2) and (5) we have $-m^{3}+mn=4(a-c)$ (6).

Notice that $kv=tr(A^{2})=k^{2}+m^{2}g+f\left[ \left( \frac{m+\sqrt{n}}{2}\right) ^{2}+\left( \frac{m-\sqrt{n}}{2}\right) ^{2}\right] =k^{2}+\left( \frac{f}{2}+g\right) m^{2}+\frac{f}{2}n$ (7).

Substituting the values of f and g in (7), we have $6k(v-k-\frac{m}{2})=3m^{2}(v-1)+n(v-1-\frac{k}{m})$ (8).

Notice that $k^{3}=a+bk+c(v-1-k)=a-c+(b-c)k+cv$ (9).

Combining (5) and (6) with (9), we have $k^{3}=\frac{3m^{2}k-m^{3}}{4}+\frac{m+k}{4}n+cv$ (10).

(i) Suppose $m=1$. By (8) we have $n=6k-3$. By (5) and (6) we have $a-c=\frac{3k-2}{2}$ and $b-c=\frac{3k}{2}$. By (10) we have $2cv=(k+1)(k-2)(2k-1)$. Moreover, the four distinct eigenvalues of G are $k, -1$ and $\frac{1\pm \sqrt{6k-3}}{2}$.

We see that k is even as $a-c=\frac{3k-2}{2}$ is an integer. If $k=4$, then by $2cv=(k+1)(k-2)(2k-1)$ we have $cv=5*7$. Therefore, we have $v=7, a=10, b=11$ and $c=5$, or $v=35, a=6, b=7$ and $c=1$ . It is easy to check that there are no graphs with such parameters (see the penultimate sentence of Note 1). If $k=6$, then by $2cv=(k+1)(k-2)(2k-1)$ we have $cv=2*7*11$. Since $f=\frac{v-1-\frac{k}{m}}{3}=\frac{v-7}{3}$, thus $v\equiv 1(mod3)$. Therefore, we have $v=22, a=15$ or $v=154, a=9$, which is impossible as a is even (see Note 1). Thus we have $k\ge 8$.

(ii) Suppose $m\ne 1$. If $m\ge 2$, then by (8) we have $6k(v-k-1)\ge 6k(v-k-\frac{m}{2})=3m^{2}(v-1)+n(v-1-\frac{k}{m})\ge 3m^{2}(v-1)+n(v-1-\frac{k}{2})$, which implies $3m^{2}+n<6k$. If $-k\le m\le -1$, then by (8) we have $6k(v-\frac{k}{2})\ge 6k(v-k-\frac{m}{2})=3m^{2}(v-1)+n(v-1-\frac{k}{m})\ge 3m^{2}(v-1)+nv$, which implies $3m^{2}+n<6k$.

By the above discussion we have $3m^{2}+n<6k$. By (5) we see that $4|(3m^{2}+n)$. Thus $3m^{2}+n\le 6k-2$ if $k\ge 3$ is odd, and $3m^{2}+n\le 6k-4$ if $k\ge 4$ is even. By elementary inequality we have $(|m|+\sqrt{n})^{2}\le (\frac{1}{\sqrt{3}}\sqrt{3}|m|+\sqrt{n})^{2}\le (\frac{1}{3}+1)(3m^{2}+n)=\frac{4}{3}(3m^{2}+n)$. Thus we have $\frac{|m|+\sqrt{n}}{2}\le \frac{\sqrt{3}}{3}\sqrt{3m^{2}+n}$. Notice that n is not the square of an integer, and thus $n\ge 2$. If $k\ge 3$ is odd, then $\frac{|m|+\sqrt{n}}{2}\le \frac{\sqrt{18k-6}}{3}$. Moreover, by $3m^{2}+n\le 6k-2$ we have $|m|\le \sqrt{2k-2}\le \frac{\sqrt{18k-6}}{3}$. Thus $\lambda _{2}(G)\le \frac{\sqrt{18k-6}}{3}$. If $k\ge 4$ is even, then $\frac{|m|+\sqrt{n}}{2}\le \frac{\sqrt{18k-12}}{3}$. Moreover, by $3m^{2}+n\le 6k-4$ we have $|m|\le \sqrt{2k-2}\le \frac{\sqrt{18k-12}}{3}$. Thus $\lambda _{2}(G)\le \frac{\sqrt{18k-12}}{3}$.

(iii) For $k=3$, by $f=\frac{v-1-\frac{k}{m}}{3}$ we have $m=\pm 1$. By (i) of Theorem 3.1 we have $m=-1$. By the proof of (ii) of Theorem 3.1, which says $3m^{2}+n\le 6k-2=16$, we have $n\le 13$. By (5) we have $4|(3m^{2}+n)$ and thus $n\equiv 1(mod4)$, which implies $n=5$ or 13. (Notice that n is not the square of an integer, since G has non-integral eigenvalues.) If $n=5$, by (10) we have $cv=24$, which implies $v=6,8,12$ or 24. By $f=\frac{v+2}{3}$ we have $v\equiv 1(mod3)$, a contradiction. If $n=13$, by (10) we have $cv=18$, which implies $v=6,9$ or 18. By $f=\frac{v+2}{3}$ we have $v\equiv 1(mod3)$, a contradiction.

For $k=4$, by $f=\frac{v-1-\frac{k}{m}}{3}$ we have $m=\pm 1$ or $\pm 2$. By (i) of Theorem 3.1 we have $m=-1$ or $\pm 2$. By the proof of (ii) of Theorem 3.1, we have $3m^{2}+n\le 6k-4=20$. By (5) we have $4|(3m^{2}+n)$.

If $m=-1$, then we have $n\le 17$ and $n\equiv 1(mod4)$, which implies $n=5,13$ or 17. If $n=5$, then by (8) we have $v=6$, a contradiction. If $n=13$, then by (8) and (10) we have $v=15$ and $cv=51$, a contradiction. If $n=17$, then by (8) and (10) we have $v=33$ and $cv=48$, a contradiction.

If $m=\pm 2$, then we have $n\le 8$ and 4|n, which implies $n=8$. For $m=-2$, by (8) and (10) we have $v=17$ and $cv=46$, a contradiction. For $m=2$, by (8) and (10) we have $v=21$ and $cv=42$, which implies $a=4,b=7$ and $c=2$. It is not difficult to show that there is no such graphs with these parameters. (If G has parameters $v=21,k=4,a=4,b=7$ and $c=2$, then by Note 1 we have that each vertex is in 2 triangles, and there is no 4-cycles. Let u be a vertex, and $N_{i}(u)$ be the set of vertices from which to u the distance is i, where $0\le i\le 3$ (diameter$\le 3$). Then the subgraph induced by $N_{1}(u)$ (the neighbours of u) is the disjoint union of two copies of $K_{2}$, and the subgraph induced by $N_{2}(u)$ is 2-regular with 8 vertices, and has a perfect matching (Notice that for any two non-adjacent vertices there are precisely $c=2$ 3-walks from one vertex to the other). Moreover, each vertex in $N_{2}(u)$ has precisely one neighbour in $N_{1}(u)$. Since each vertex is in 2 triangles, thus we must have $|N_{3}(u)|=4$, which implies $v=1+4+8+4=17$, a contradiction. We complete the proof. $\square$

Theorem 3.2

Let G be a connected strongly 3-walk-regular graph defined as Note 1. If G has integral eigenvalues (each eigenvalue is an integer), then its second largest eigenvalue is at most $k-2$. Moreover, we have $k\ge 4$.

Proof

Without loss of generality, we can suppose $k>\theta _{1}>\theta _{2}>\theta _{3}$. We prove the conclusion by contradiction. Suppose $\theta _{1}=k-1$.

Since all eigenvalues of A except k are the roots of equation $x^{3}+(c-b)x-(a-c)=0$, we have $\theta _{2}+\theta _{3}=1-k, \theta _{2}\theta _{3}+(k-1)(\theta _{2}+\theta _{3})=c-b$ and $(k-1)\theta _{2}\theta _{3}=a-c$. If $\theta _{3}=-k$, then G is a bipartite graph, and thus $c=0$. By Proposition 5.1 of [9] we have that G is a complete bipartite graph and is thus a strongly regular graph, a contradiction. Thus $\theta _{3}\ge 1-k$, and then $\theta _{2}\le 0$. If $\theta _{2}=0$ and thus $\theta _{3}=1-k$, then we have $(k-1)|k$ as $tr(A)=0$, which is impossible. Thus we have $-1\ge \theta _{2}>\theta _{3}\ge 2-k$. As $a\le k(k-1), c>0$, we have $(k-1)\theta _{2}\theta _{3}\le k(k-1)-1$, which implies $\theta _{2}\theta _{3}\le k-1$.

Since $\theta _{2}\theta _{3}\le k-1$ and $\theta _{2}+\theta _{3}=1-k$, we have $\theta _{2}=-1$ and $\theta _{3}=2-k$ for $-1\ge \theta _{2}>\theta _{3}\ge 2-k$. Thus $a-c=(k-1)(k-2)$ and $b-c=k^{2}-3k+3$. Since a is even, thus c is even. By $k^{3}=a+bk+c(v-1-k)$, we have $cv=2(k+1)(k-1)$, which implies $v|(k-1)(k+1)$ as c is even. Combining $tr(A)=0$ and $tr(A^{2})=vk$ with $1+m_{1}+m_{2}+m_{3}=v$, by substitution of eigenvalues we have $m_{1}=\frac{2(k-1)(v-1-k)}{2k^{2}-3k}$. Since $(k-1,2k^{2}-3k)=1$, we have $(2k^{2}-3k)|(2v-2(k+1))$. Since $v|(k-1)(k+1)$, we have $2v-2(k+1)\le 2k^{2}-2k-4<2(2k^{2}-3k)$. Then by $(2k^{2}-3k)|(2v-2(k+1))$ we have $2k^{2}-3k=2v-2(k+1)$, which implies $2v=2k^{2}-k+2$. Then $(2k^{2}-k+2)|2(k+1)(k-1)$, which implies $2k^{2}-k+2=2(k+1)(k-1)$ or $k=4$. Then G has parameters $v=15,k=4,a=8,b=9$ and $c=2$. It is not difficult to show that it is impossible, since each vertex is in 4 triangles and each edge is in 2 4-cycles by Note 1. Then we complete the proof of the first part.

Now suppose that the case $k=3$ is possible. By the above discussion we have that the second largest eigenvalue of G is at most $k-2=1$. Thus the four distinct eigenvalues are 3, 1, 0 and $-1$ ($\theta _{1}+\theta _{2}+\theta _{3}=0$), which is impossible as $m_{2}=8-2v<0$. We complete the proof. $\square$

Remark 1

By Theorems 3.1 and 3.2 (see Note 1) we have that each connected cubic strongly 3-walk-regular graph is a strongly regular graph.

Lemma 3.3

Let G be a connected strongly 3-walk-regular graph defined as Note 1. Then G contains no k-clique (a clique of size k) except the graph formed by adding a perfect matching between two copies of $K_{4}$, which has parameters $v=8,k=4,a=6,b=10$ and $c=6$.

Proof

By Theorems 3.1 and 3.2 we can suppose $k\ge 4$. Now suppose that G contains a k-clique W. Thus $a\ge (k-1)(k-2)$. Let x be a vertex of $\overline{W}$ such that x is adjacent to a vertex y of W. Then we have $|E(x,W)|\mid k$, since each vertex is in the same number of triangles. Since both the vertex x and the vertex y are in $\frac{a}{2}$ triangles, thus the vertex x has the the unique neighbour in W which is the vertex y for $k\ge 4$. It implies $a=(k-1)(k-2)$. Consequently, for each vertex u in $\overline{W}$, if u is adjacent to W, then it has precisely one neighbour in W. Then each vertex is in a k-clique as G is connected.

It is easy to see that two distinct k-cliques are vertex-disjoint by the above discussion. Therefore, the vertices of G can be partitioned into some k-cliques. For any two adjacent k-cliques W and H, the number of edges between them is at least 2, since both an edge between them and an edge in W are in the same number of 4-cycles. Thus, we can suppose that there are $p\ge 2$ edges between them, and thus there are two vertices $u_{1},w_{1}$ in W which are adjacent to $x_{1},y_{1}$ in H, respectively. Since both the edge $u_{1}w_{1}$ and the edge $u_{1}x_{1}$ are in the same number of 4-cycles, we have $p-1=1+(k-2)(k-3)$, which implies $p=k=4$. Moreover, G is the graph formed by adding a perfect matching between two copies of the complete graph $K_{4}$, which has parameters $v=8,k=4,a=6,b=10$ and $c=6$. We complete the proof. $\square$

Theorem 3.4

Let G be a connected strongly 3-walk-regular graph of degree $k\ge 3$. Then the edge-connectivity of G is equal to k. Moreover, if G is not the graph formed by adding a perfect matching between two copies of $K_{4}$, which has parameters $v=8,k=4,a=6,b=10$ and $c=6$, then each edge cut set of size k is precisely the set of edges incident with a vertex of G.

Proof

By Note 1 we need only to consider that G is not a strongly regular graph. Let M be an edge cut of minimum size in G. Then there exists a subset S of V(G) such that $|S|\le \frac{v}{2}$ and $M=E(S,\overline{S})$, where $\overline{S}=V(G)-S$. The two induced subgraphs G[S] and $G[\overline{S}]$ are both connected by the choice of M.

If $|S|=1$, then the conclusion is easy to see.

If $1<|S|\le k$, then $|M|\ge |S|(k+1-|S|)\ge k$ by regularity. If equality holds, then G[S] is a clique of size k, which is impossible by Lemma 3.3 except the graph formed by adding a perfect matching between two copies of $K_{4}$ with parameters $v=8,k=4,a=6,b=10$ and $c=6$.

Now consider the remained case $k+1\le |S|\le \frac{v}{2}$. Suppose that G has non-integral eigenvalues. Then we are in the case of Theorem 3.1. As in Theorem 3.1, for $m=1$, we have $k\ge 8$, and $|M|\ge \frac{(k-\frac{1+\sqrt{6k-3}}{2})|S|(v-|S|)}{v}$ by Lemma 2.3, which implies $|M|\ge \left( k-\frac{1+\sqrt{6k-3}}{2}\right) \frac{k+1}{2}>k$ for $k\ge 8$, since the function $h(x)=2x^{2}-3x-(x+1)\sqrt{6x-3}-1$ is monotonously increasing when $x\ge 3$ and $h(5)>0$.

For $m\ne 1$, then by (iii) of Theorem 3.1, we have $k\ge 5$.

Suppose that $k\ge 5$ is odd. By Lemma 2.3 and Theorem 3.1 we have $|M|\ge \frac{(k-\frac{\sqrt{18k-6}}{3})|S|(v-|S|)}{v}\ge \frac{(k+1)(k-\frac{\sqrt{18k-6}}{3})}{2}>k$ if and only if $3k^{4}-12k^{3}-7k^{2}-2k+2>0$. It is obviously true if $k\ge 5$.

Suppose that $k\ge 6$ is even. By Lemma 2.3 and Theorem 3.1 we have $|M|\ge \frac{(k-\frac{\sqrt{18k-12}}{3})|S|(v-|S|)}{v}\ge \frac{(k+1)(k-\frac{\sqrt{18k-12}}{3})}{2}>k$ if and only if $3k^{4}-12k^{3}-5k^{2}+2k+4>0$. It is obviously true if $k\ge 6$.

Now we can suppose that G has integral eigenvalues. By Theorem 3.2 we have $k\ge 4$ and $\lambda _{2}(G)\le k-2$. For $k+1\le |S|\le \frac{v}{2}$, we have $|M|\ge \frac{(k-(k-2))|S|(v-|S|)}{v}\ge \frac{2(k+1)}{2}>k$ by Theorem 3.2. We complete the proof. $\square$

Remark 2

By Theorem 2.4 it is not difficult to see that for each connected k-regular graph G on v vertices with edge-connectivity at least $k-1$, G is 1-extendable for even v and is factor-critical for odd v (see [14]). Let G be a connected strongly 3-walk-regular graph on v vertices. Then by Theorem 3.4 we see that G is 1-extendable for even v and is factor-critical for odd v.

Considering the 3-walks (walks of length 3) in a regular graph G in general, we give a sufficient and tight condition such that G is 1-extendable as follows.

Theorem 3.5

Let G be a k-regular ($k\ge 3$) graph on even number of vertices. If for any two non-adjacent vertices of G the number of 3-walks from one vertex to the other is at least $[\frac{k-1}{2}]$, then G is 1-extendable.

Proof

Set $d=[\frac{k-1}{2}]$. We prove the conclusion by contradiction. Suppose that G is not 1-extendable. By Theorem 2.4, there is a subset S of V(G) such that $o(G-S)\ge |S|$ and G[S] contains an edge e.

Let $P_{1},P_{2},\ldots ,P_{|S|}$ be the odd components of $G-S$. By regularity, S can accept at most $k|S|-2$ edges from $G-S$ as the edge e is inside S. If each vertex in $P_{i}$ has a neighbour in S for $1\le i\le |S|$, then we have $|E(P_{i},S)|\ge |P_{i}|\ge k$ for $|P_{i}|\ge k$ and $|E(P_{i},S)|\ge |P_{i}|(k+1-|P_{i}|)\ge k$ for $|P_{i}|\le k-1$. It implies that $|E(G-S,S)|\ge k|S|$, which is a contradiction as S can accept at most $k|S|-2$ edges from $G-S$. Thus, without loss of generality, we can suppose that there exists a vertex u in $P_{1}$ such that u has no neighbour in S and thus $|P_{1}|>k$. It is easy to see that $|E(P_{1},S)|\ge d$ as the number of 3-walks is at least d from the vertex u to each vertex in $P_{2}$. For any component $P_{i}$ for $i>1$, each vertex w in $P_{i}$ has a neighbour in S as there is a 3-walk from the vertex u to w. Similarly, we have $|E(S,P_{i})|\ge k$.

If there exists an odd component which is a singleton set. Then we have $|S|\ge k$. Let $S_{1}$ be the subset of S of which each vertex has a neighbour in $P_{1}$. Then each vertex w in $S-S_{1}$ has a neighbour in $S_{1}$ as there is a 3-walk from the vertex u to w. Thus $|E(S)|+|E(S,P_{1})|\ge k$, where E(S) is the set of edges in S. We have $2|E(S)|+|E(S,P_{1})|>k$ as $|E(S)|>0$. Therefore, S can accept at most $k(|S|-1)-1$ edges from $G-S-P_{1}$, which is a contradiction to the fact that $|E(S,P_{i})|\ge k$ for $1<i\le |S|$.

Now we can suppose that there is no singleton set among the odd components of $G-S$. Similarly, if $|P_{i}|<k$ for some i, then $|E(S,P_{i})|\ge |P_{i}|(k-|P_{i}|+1)\ge 2(k-1)$. Thus we have $|E(G-S,S)|\ge 2k-2+k(|S|-2)+d=k|S|-2+d$, which is impossible as S accepts at most $k|S|-2$ edges by regularity. Thus we have $|P_{i}|\ge k$ for any $1\le i \le |S|$. For any vertex w in S, there are at most $k-1$ neighbours in $G-S-P_{1}$ as there is a 3-walk from the vertex u to w. Similarly, the number of neighbours of $S-w$ in $G-S-P_{1}$ is at most $(k-1)(|S|-1)$ which is less than $|G-S-P_{1}|$ as $|P_{i}|\ge k$ for $2\le i\le |S|$. Thus there is a vertex x in $G-S-P_{1}$ such that x has only one neighbour w in S, which implies $|E(w,P_{1})|\ge d$ as there are d 3-walks from the vertex u to x. Consequently, we have $|E(w,P_{1})|\ge d$ for any vertex w in S.

If k is odd, then $|E(P_{1},S)|\ge d|S|\ge 2d$ is odd as $P_{1}$ is an odd component, which implies $|E(P_{1},S)|\ge 2d+1$. Since there is an edge in S and $|E(P_{i},S)|\ge k$ for $i>1$, we have $|E(P_{1},S)|\le k|S|-k(|S|-1)-2=k-2$. Thus we have $d\le \frac{k-3}{2}$, which is a contradiction.

If k is even, then $|P_{2}|>k$ as $|P_{2}|\ge k$ is odd and thus $|E(P_{2},S)|> k$ as each vertex in $P_{2}$ has a neighbour in S, which implies $|E(P_{2},S)|\ge k+2$ by parity. Thus we have $2d\le |E(P_{1},S)|\le k|S|-k(|S|-2)-(k+2)-2$ and thus $d\le \frac{k-4}{2}$, which is a contradiction. We complete the proof. $\square$

The lower bound in Theorem 3.5 is tight. Indeed, if $k\ge 9$ is an odd integer, we can construct a k-regular graph G on $2k+4$ vertices such that for any two non-adjacent vertices of G, the number of 3-walks from one vertex to the other is at least $\frac{k-3}{2}$, but G is not 1-extendable. In detail, let A be the graph derived from $K_{\frac{k-1}{2}}$ by deleting the edges of a hamiltonian cycle of $K_{\frac{k-1}{2}}$ and B be the graph derived from $K_{\frac{k-3}{2}}$ by deleting the edges of a hamiltonian cycle of $K_{\frac{k-3}{2}}$. Let C be a 4-cycle, $D=K_{2}=xy$ be an edge and E be $K_{k}$. Now G is formed from the five parts as follows. For any two distinct parts of A, B and C, connect each vertex in one part to each vertex in the other part. Also, add an edge from the vertex x to each vertex of A and to each vertex of (any) $\frac{k-1}{2}$ vertices of E, and add an edge from the vertex y to each vertex of B and to each vertex of the remained $\frac{k+1}{2}$ vertices of E, as required.

If $k\ge 8$ is an even integer, we can construct a k-regular graph G on $2k+4$ vertices such that for any two non-adjacent vertices of G, the number of 3-walks from one vertex to the other is at least $\frac{k-4}{2}$, but G is not 1-extendable. In detail, let A be a $\frac{k-4}{2}$-clique $K_{\frac{k-4}{2}}$ and B be a $\frac{k-4}{2}$-clique $K_{\frac{k-4}{2}}$. Let C be a 5-clique, $D=K_{2}=xy$ be an edge and E be a graph on $k+1$ vertices such that there is one vertex, say u, of degree $k-2$ and the other k vertices of degree $k-1$ (such a graph can be derived from $K_{k+1}$ by deleting the edges of a path of length 2 and $\frac{k-2}{2}$ independent edges). Now G is formed from the five parts as follows. Connect each vertex in C to each vertex in A and B. Add all the edges except a perfect matching between A and B. Also, add two edges ux and uy, and add an edge from the vertex x to each vertex of A and to each vertex of (any) $\frac{k}{2}$ vertices of degree $k-1$ in E, and add an edge from the vertex y to each vertex of B and to each vertex of the remained $\frac{k}{2}$ vertices of degree $k-1$ in E, as required.