WorksMathematics
2-Walk-regular graphs with at most twice the valency
Abstract
In this paper, we characterize -walk-regular graphs with valency , diameter at least four and , generalizing a result of Koolen and Park, and classify the distance-regular graphs satisfying these conditions. We also classify -walk-regular graphs with valency , diameter at least four and at most vertices.
Introduction
A graph is 2-walk-regular if, for every nonnegative integer , the number of walks of length between vertices at distance at most two depends only on their distance. Such graphs are generalizations of distance-regular graphs. In this paper, we study 2-walk-regular graphs with valency , diameter and .
We first show that such graphs are bipartite if .
Theorem 1.1. Let be a 2-walk-regular graph with valency and diameter . If and , then is bipartite.
Remark. (i) Koolen and Park [10 Theorem 17] showed that for , there exists a real number such that a distance-regular graph with valency , diameter and is either a Taylor graph or a bipartite graph with diameter 3.
(ii) The Hamming graph (, ), the line graph of the Petersen graph (, ), and the Coxeter graph (, ) are nonbipartite distance-regular graphs with .
As an application of Theorem 1.1, we obtain the following characterization of 2-walk-regular graphs with valency , diameter and .
Theorem 1.2. Let be a 2-walk-regular graph with valency and diameter . Then if and only if is one of the following graphs:
(i) a Hadamard graph, with even, , and ;
(ii) the 5-cube, with , , and ;
(iii) the incidence graph of a GDDDP, with odd, , and ;
(iv) a cubic 1-walk-regular graph with diameter at least four and girth at least five; here and ;
(v) a line graph , where is a cubic 3-walk-regular graph with diameter at least four and girth at least six; here and .
Remark. (i) Qiao, Park and Koolen [13 Theorem 1.3] classified 2-walk-regular graphs with valency , diameter and .
(ii) Conder and Nedela [4 Proposition 2.5] constructed infinitely many finite cubic 3-arctransitive graphs with girth at least 10. For each such graph , the graphs and belong to (iv) and (v) respectively. And Lemma 4.3 implies that the graphs are pairwise nonisomorphic. Hence both (iv) and (v) contain infinitely many graphs.
Then we classify distance-regular graphs with valency , diameter and .
Theorem 1.3. Let be a distance-regular graph with valency and diameter . Then if and only if is a Hadamard graph or one of the eleven graphs in Table 1.
| Graph | Intersection array | |||
| Pappus | 3 | 18 | 4 | |
| Coxeter | 3 | 28 | 4 | |
| Tutte 8-cage | 3 | 30 | 4 | |
| Dodecahedron | 3 | 20 | 5 | |
| Desargues | 3 | 20 | 5 | |
| Tutte 12-cage | 3 | 126 | 6 | |
| Biggs–Smith | 3 | 102 | 7 | |
| Foster | 3 | 90 | 8 | |
| 4 | 45 | 4 | ||
| 4 | 189 | 6 | ||
| 5-cube | 5 | 32 | 5 |
Table 1. Non-Hadamard distance-regular graphs with , , and
Remark. (i) Koolen and Park [10 Theorem 20] classified distance-regular graphs with valency , diameter and .
(ii) The graphs and are the line graphs of the Tutte 8-cage and Tutte 12-cage, respectively. And for , the 4-cube is a Hadamard graph, and hence is not included in Table 1.
Then we classify 2-walk-regular graphs with valency , diameter and vertices.
Theorem 1.4. Let be a 2-walk-regular graph with valency , diameter , and vertices. Then if and only if is one of the following graphs:
(i) a Hadamard graph with even and ;
(ii) the incidence graph of a GDDDP with odd and .
Remark. Qiao, Koolen and Park [12 Theorem 1.2] gave a characterization of 2-walk-regular graphs with valency , diameter and vertices for a fixed . They also showed that a 2-walk-regular graph with valency , diameter and vertices is distance-regular if , or and is bipartite (see [12 Corollary 4.2]). They also gave an infinite family of the incidence graphs of GDDDP. Such graphs were also studied by Jin, Koolen and Lv [8].
This paper is organized as follows: In § 2, we give some definitions and preliminary results. In § 3, we give a proof of Theorem 1.1. In § 4, we determine feasible parameters for 2-walk-regular graphs with and (Lemma 4.1), and characterize the corresponding 2-walk-regular graphs with valency four (Lemma 4.3). Then we give proofs of Theorems 1.2 and 1.3. In § 5, we determine 2-walk-regular graphs with and (Lemma 5.2). Then we give a proof of Theorem 1.4.
Definitions and preliminaries
All graphs considered in this paper are finite, undirected and simple. The reader is referred to [1, 7] for more information.
Let be a connected graph. Two vertices are adjacent if is in , denoted by . The distance between two vertices is the length of a shortest path between and in . The diameter is the maximum distance between any two vertices in . For each , let be the set of vertices at distance from (). In addition, we define . For simplicity, we write . For , the valency of in is . A graph is regular with valency if for all . The local graph of at is the subgraph induced on . For two vertices at distance two, the -graph is the subgraph induced on .
Let be a graph with diameter and let be vertices of at distance ($0 \le i \le D$). Let , , , . The intersection numbers , , are called well-defined if the numbers do not depend on the choice of and but only on . A graph with diameter is called -partially distance-regular if these numbers , and are well-defined for (where it is implicitly assumed that ). If this is the case, then these numbers are denoted simply by , and (). The relation shows that () are also well-defined. If , then the graph is called a distance-regular graph, and the array is called the intersection array of $\Gamma. A distance-regular graph with intersection array is called a Hadamard graph.
A graph is called -walk-regular if the number of walks of every given length between two vertices depends only on the distance between and , provided that (where it is implicitly assumed that the diameter of is at least ). A -walk-regular graph is a -partially distance-regular graph (see [5 Proposition 3.15]).
The distance- matrix of is the matrix whose rows and columns are indexed by the vertices of and the -entry is 1 whenever and 0 otherwise. The adjacency matrix of is , and it is simply denoted by or . The eigenvalues of are the eigenvalues of its adjacency matrix . We denote the transpose of a matrix by .
Let be a -walk-regular graph with vertices, and let be an eigenvalue of with multiplicity . The matrix corresponding to the orthogonal projection onto the eigenspace associated to is called the minimal idempotent associated to . The map
is called the normalized representation associated to . Note that there exist constants such that (), where is the entrywise product (see [6 Theorem 3.1]), i.e., the -entry of only depends on the distance between and if . Then , , and () is well-defined, where are any two vertices of at distance . As , we have and
The sequence is called the -partial standard sequence of corresponding to the eigenvalue . For a distance-regular graph with diameter , the standard sequence is the -partial standard sequence (see [1 p. 128]). Note that for a -walk-regular graph, by (1), we have
A partition of is equitable if there exist non-negative integers () such that every vertex in has exactly neighbors in . When is equitable, the distribution diagram of with respect to is a diagram in which each block is represented by a balloon. We draw a line from the balloon representing to that of if , placing the number above the line near . Inside the balloon we write , and below it we write . If , we write instead of .
An incidence structure consists of a set of points, a set of blocks (disjoint from ), and a relation called incidence. If , then we say that the point and the block are incident. We regard each block as a subset of . Given an incidence structure , its dual incidence structure is defined as , where . The point-block incidence graph of is the graph with vertex set , where two vertices are adjacent if and only if they are incident. Note that the point-block incidence graph of an incidence structure is bipartite.
A group divisible design with parameters , denoted by , is an ordered triple , where is a set of points, is a partition of into subsets of size (called groups), and is a collection of -subsets of (called blocks), such that each pair of points from the same group appears in exactly blocks, and each pair of points from different groups appears in exactly blocks. The triple , with the natural incidence relation , forms an incidence structure, and we consider its dual . If there exists a partition of such that the triple is a , then we say that is a group divisible design with the dual property with parameters , denoted by .
For the convenience of the reader, we list the following known results.
Lemma 2.1 (cf. [1 Proposition 4.1.6]). Let be a -walk-regular graph with diameter . If and , then holds.
Lemma 2.2 (cf. [3 Proposition 5.1]). Let be a -walk-regular graph with diameter and distinct eigenvalues . Let be a local graph of with smallest eigenvalue . Then
Lemma 2.3 (cf. [13 Lemma 2.5]). Let be a -walk-regular graph with diameter and distinct eigenvalues . If contains an induced quadrangle, then
Lemma 2.4 (cf. [13 Theorem 1.3]). Let be a -walk-regular graph with valency and diameter . If , then is a Hadamard graph, the -cube, or the incidence graph of a for some integer .
Lemma 2.5 (cf. [11 Theorem 2]). Let be odd, and let be a GDDDP with incidence graph . Then is 2-walk-regular with vertices. Moreover, for each vertex , there exists a unique vertex at distance four from , and the partition
is equitable with distribution diagram as in Figure 1.
Figure 1. Distribution diagram of the incidence graph of GDDDP
Lemma 2.6 (cf. [3 Propositions 3.6 and 3.4]). Let be a graph with valency , diameter and girth .
(i) If is 1-walk-regular and , then is 2-walk-regular.
(ii) If is 3-walk-regular and , then is 2-walk-regular.
Lemma 2.7 (cf. [9 Lemma 6]). Let be a 2-walk-regular graph with valency , diameter , and distinct eigenvalues . Then
Proof. Let with . Then the graph induced on has largest eigenvalue with multiplicity 2. The result follows by interlacing.
Proof of Theorem 1.1
Proof of Theorem 1.1. Let be a 2-walk-regular graph with valency , diameter , satisfying and .
Let and be the roots of . Then
Let be a local graph, and let be the average number of common neighbors in over its unordered pairs of nonadjacent vertices, that is
For any two vertices of at distance 2, let be the average degree of the -graph , that is
Claim 1. We have , and the local graph has smallest eigenvalue at least . Moreover,
:::
Proof of Claim 1. By Lemma 2.7, we have . Thus Lemma 2.2 shows that the smallest eigenvalue of the local graph is at least
In the local graph , there are ordered nonadjacent pairs of vertices and walks of length two with distinct endpoints, among which have adjacent endpoints. Hence
Since , this shows the second inequality in (4). Let . Since the spectrum of lies in , the polynomial is nonnegative on the spectrum. Since is an eigenvalue of , we have . Using and , this gives
Hence . Substituting this bound into (5), we obtain
This shows the first inequality in (4).
Claim 2. contains an induced quadrangle, and .
Proof of Claim 2. Assume that contains no induced quadrangle. Then every -graph of is a clique. Hence in the local graph , two nonadjacent vertices have exactly common neighbors. Claim 1 gives
Together with and (3), we have
and hence . Moreover, (6) implies , since and . The local graph is connected, since its nonadjacent vertices have common neighbors. By Claim 1, the smallest eigenvalue of is at least . By [1 Corollary 3.12.3], it must be an odd cycle, contrary to . Hence contains an induced quadrangle. Now Claim 1 and Lemma 2.3 give . Since , we have .
Claim 3. For any two vertices with ,
The average of over all unordered pairs of vertices of at distance 2 equals the average of over all local graphs of .
Proof of Claim 3. By Claim 2, we have . Write and . Equation (2) gives
Consider a normalized representation associated to . Fix with . Let and
Since vertices of are pairwise at distance one or two in ,
Applying Cauchy–Schwarz to and gives
Since and , this is equivalent to
Moreover, using (3),
since and . As and , it follows that
Let be the set of unordered distance-two pairs of . We count the number of induced diamonds (see Figure 2) in . Then
where the -graph has edges, and the local graph of at vertex has unordered pairs of nonadjacent vertices. Thus we have
where
Claim 4. .
Proof of Claim 4. Let be the average of over all unordered pairs of the vertices of at distance 2. Then by Claim 1 and Claim 3, we have
Figure 2. Induced diamond
Since and (Claim 2), using (3), we have
By (9), we have
Assume . The lower bound and first upper bound in (10) imply . Then the lower bound and second upper bound in (10) give , hence . By (10), we have . Then implies . Hence by (3). By (9), , so . Since , we have .
Choose with . Note that the -graph has 3 vertices. Then (7) implies . It follows that has at least two edges and , contradicting . Hence .
Assume . Then every local graph is 1-regular and every independent set in a local graph has at most vertices. Note that contains no induced diamond and each -graph contains no edges. Choose with and . Then vertices in and form an independent set of with vertices. Hence . As and , we have . Then , a contradiction. Hence .
By Claim 4, and . Assume is nonbipartite. Then Lemma 2.4 implies . As , we have . Thus and , contrary to .
Proofs of Theorems 1.2 and 1.3
Lemma 4.1. Let be a 2-walk-regular graph with valency , diameter , and . If , then
In particular, if , then .
Proof. Note that . As , contains no induced diamond and every local graph is a disjoint union of cliques of size . Since , we have , that is . It follows that , and or 4.
Lemma 4.2. Let be a cubic 3-walk-regular graph with diameter and girth at least six. Then if and only if .
Proof. Assume and consider a path with . Since is 3-walk-regular, we have . Take a neighbor of with . Then . It follows that . If , then is distance-regular, which is the Heawood graph (see [1 Theorem 7.5.1]). Since is bipartite with diameter three, any two edges have endpoints in the same bipartition class at distance at most two. Hence .
Lemma 4.3. (i) For a 2-walk-regular graph with valency , diameter and , there exists a unique cubic 3-walk-regular graph with diameter and girth , such that .
(ii) Conversely, for a cubic 3-walk-regular graph with diameter and girth , the line graph is 2-walk-regular with valency 4, diameter and .
Proof. (i) Note that the local graph of consists of two disjoint edges. Let be the set of triangles of , and two vertices of are adjacent if the triangles share a common vertex. Then is cubic. Let be the triangle-vertex incidence matrix of , which is also the vertex-edge incidence matrix of . Then implies .
A triangle in would give an extra triangle in , and an induced quadrangle in would give an induced quadrangle in . Hence . Since and , we have .
Choose a path in with . Let and be extra edges. Note that and . If , then , contradicting . Hence in . If contains an induced pentagon , then and , where is an extra edge, contrary to . This shows .
Consider the vertex-edge incidence matrix of . Let
For every , we have
By the first identity, the diagonal of is a constant , as the three edges incident with a vertex of form a triangle in . Let the entries of at distance in be . Then we successively determine entries of at distance in through
Since powers of are linear combinations of powers of , the graph is 3-walk-regular. And Lemma 4.2 implies .
Assume with cubic and girth . Then each vertex of is incident with three edges. Hence each vertex of corresponds to a triangle in . As is triangle-free, every triangle of arises in this way. And two vertices of are adjacent if the triangles in share a common vertex. This shows the uniqueness of .
(ii) Conversely, Lemma 2.6 implies that is 2-walk-regular, and Lemma 4.2 implies . Since , the local graph of consists of two disjoint edges and . Then contains no induced quadrangles and .
Proof of Theorem 1.2. Assume . Note that . Then is bipartite by Theorem 1.1. We have and . Since and (Lemma 2.1), we have
If is even, then and . Then is a Hadamard graph by [1 Theorem 1.9.3], giving (i).
If is odd, then and . Hence . Lemma 2.4 shows that is the 5-cube, giving (ii), or the incidence graph of a GDDDP. In the latter case, the vertices at distance two from a point are precisely the points outside its group. Hence , that is . Lemma 2.5 shows that , giving (iii).
If , Lemma 4.1 gives or . In the cubic case, and show that the girth is at least five, giving (iv). In the quartic case, Lemma 4.3 gives (v).
Conversely, the 5-cube and Hadamard graphs are distance-regular, hence 2-walk-regular, with and , respectively. The graphs in (iii) are 2-walk-regular with by Lemma 2.5. For the graphs in (iv), Lemma 2.6 gives 2-walk-regularity. The girth condition implies , so . For the graphs in (v), Lemma 4.3 gives 2-walk-regularity and , so .
Proof of Theorem 1.3. Apply Theorem 1.2 to distance-regular graphs with . The only possible cases are (i), (ii), (iv) and (v). The result follows from the classifications of distance-regular graphs of valency 3 or 4 (see [1 Theorem 7.5.1] and [2 Theorem 1.1]).
Proof of Theorem 1.4
Lemma 5.1. Let be a 2-walk-regular graph with valency , diameter , and vertices. Then .
Proof. Choose two vertices with . Note that are pairwise disjoint. Hence we have
that is . Suppose . Then , and
a contradiction.
Lemma 5.2. Let be a 2-walk-regular graph with valency , diameter , and vertices. If , then and is the incidence graph of a GDDDP.
Proof. Lemma 5.1 gives . Then we only need to consider (iv) and (v) of Theorem 1.2.
In (v) of Theorem 1.2, and , where is a cubic 3-walk-regular graph with diameter at least four and girth at least six. We have , and by (10). Then
In (iv) of Theorem 1.2, we have and girth at least five. Then , and . Note that , that is . Equation (10) implies . Lemma 2.1 gives , so .
Suppose . For every vertex , each edge in determines a unique pentagon through . Thus each vertex lies in pentagons and the total number of pentagons is , that is , which contradicts .
It follows that and . Take two vertices of with . Note that there are at most edges between and , and edges between and . It follows that and . Then we have , and . Note that there are six edges between and each of and . We have for , and for . Since , each vertex in has exactly one neighbor in each of and . Then the partition has the distribution diagram as in Figure 3. Since is bipartite with and , every vertex has a unique vertex at distance four. Hence is the incidence graph of GDDDP.
Figure 3. Distribution diagram of the incidence graph of GDDDP(2, 4; 3; 0, 1)
Proof of Theorem 1.4. By Lemma 5.1, implies . If , then Lemma 5.2 applies. For , the results follow from Theorem 1.2.
Funding This work was supported by the National Natural Science Foundation of China (No. 12371338) and the Key Project in Natural Science Research of Anhui Provincial Department of Education (No. 2023AH050268).
Data Availability No data was used for the research described in the article.
Declarations
Conflict of interest The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.
References
- [1]A. E. Brouwer, A. M. Cohen and A. Neumaier, Distance-Regular Graphs, Springer-Verlag, Berlin, 1989.
- [2]A. E. Brouwer and J. H. Koolen, The distance-regular graphs of valency four, J. Algebraic Combin. 10 (1999), 5–24.DOI
- [3]M. Cámara, E. R. van Dam, J. H. Koolen and J. Park, Geometric aspects of 2-walk-regular graphs, Linear Algebra Appl. 439 (2013), 2692–2710.DOI
- [4]M. Conder and R. Nedela, Symmetric cubic graphs of small girth, J. Combin. Theory Ser. B 97 (2007), 757–768.DOI
- [5]C. Dalfó, E. R. van Dam, M. A. Fiol, E. Garriga and B. L. Gorissen, On almost distance-regular graphs, J. Combin. Theory Ser. A 118 (2011), 1094–1113.
- [6]C. Dalfó, M. A. Fiol and E. Garriga, On k-walk-regular graphs, Electron. J. Combin. 16 (2009), #R47.DOI
- [7]E. R. van Dam, J. H. Koolen and H. Tanaka, Distance-regular graphs, Electron. J. Combin. (2016), #DS22.DOI
- [8]W. Jin, J. H. Koolen and C. Lv, Amply regular graphs with μ close to half the valency and group divisible designs, arXiv:2605.25754, 2026.arxiv.org/abs/2605.25754
- [9]J. H. Koolen and J. Park, Shilla distance-regular graphs, European J. Combin. 31 (2010), 2064–2073.arxiv.org/abs/0902.3860
- [10]J. H. Koolen and J. Park, Distance-regular graphs with a₁ or c₂ at least half the valency, J. Combin. Theory Ser. A 119 (2012), 546–555.DOI
- [11]Z. Qiao, S. F. Du and J. H. Koolen, 2-Walk-regular digraphs from group divisible designs, Electron. J. Combin. 23 (2016), #P2.51.DOI
- [12]Z. Qiao, J. H. Koolen and J. Park, 2-Walk-regular graphs with a small number of vertices compared to the valency, Linear Algebra Appl. 510 (2016), 10–24.DOI
- [13]Z. Qiao, J. Park and J. H. Koolen, On 2-walk-regular graphs with a large intersection number c₂, European J. Combin. 80 (2019), 224–235.DOI


