{'fraction_non_alphanumeric': 0.06567939224925473, 'fraction_numerical': 0.020803282366894254, 'mean_word_length': 3.6654703155376103, 'pattern_counts': {'":': 0, '<': 4, '<?xml version=': 0, '>': 13, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 28, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Some Spectral and Quasi-Spectral Characterizations of Distance-Regular Graphs

In this paper we consider the concept of preintersection numbers of a graph. These numbers are determined by the spectrum of the adjacency matrix of the graph, and generalize the intersection numbers of a distance-regular graph. By using the preintersection numbers we give some new spectral and quasi-spectral characterizations of distance-regularity, in particular for graphs with large girth or large odd-girth.


Introduction
A central issue in spectral graph theory is to study whether or not the spectrum of a graph determines it uniquely or, at least, some of its basic characteristics, see the surveys of Van Dam and Haemers [18,19]. In particular, much attention has been paid to give spectral or quasi-spectral characterizations of distance-regularity.
A distance-regular graph with diameter d has d + 1 distinct eigenvalues and its spectrum can be obtained from the intersection array and vice versa. However, in general the spectrum of a graph does not tell us wether it is distance-regular or not. In this paper we will prove new results about when distance-regularity of a graph is a property that can be determined by the spectrum. Other contributions in this area are due to Laskar [33], Cvetković [9], Brouwer and Haemers [6], Van Dam and Haemers [17], Van Dam, Haemers, Koolen, and Spence [21], Haemers [30], and Huang and Liu [32], among others. A survey of the most relevant results can also be found in the textbook of Brouwer and Haemers [7], and the survey of Van Dam, Koolen, and Tanaka [22].
In [17] Van Dam and Haemers gave conditions for distance-regularity under the assumption that the graph is cospectral with a distance-regular graph. Our aim is to make these conditions less restrictive by using the so-called preintersection numbers, and dropping the assumption that the graph is cospectral with a distance-regular graph. The preintersection numbers are numbers that follow from the spectrum and resemble the intersection numbers of distance-regular graphs. Indeed, we will give new spectral and quasi-spectral characterizations of distance-regularity without requiring, as it is common in this area of research, that: • G is cospectral with a (feasible) distance-regular graph Γ, and • Γ has intersection numbers, or other combinatorial parameters that satisfy certain properties.
For an overview of such results, see Theorem 2.4. Instead, we shall show that for some of these results, the same conclusions can be obtained within a much more general setting, i.e., that: • G has preintersection numbers (and for some results also the average of some intersection numbers) that satisfy certain properties.
For example, Van Dam and Haemers [17] showed that a graph G is distance-regular if it is cospectral with a distance-regular graph Γ with diameter d and intersection numbers c 1 = · · · = c d−1 = 1. We generalize this in Theorem 4.8, by showing that if a graph G has d + 1 distinct eigenvalues and preintersection numbers γ 1 = · · · = γ d−1 = 1, then G is distance-regular.
This work was motivated by earlier work in this area, in particular by the odd-girth theorem [20]. This result states that a graph with d + 1 distinct eigenvalues and odd-girth 2d + 1 is distance-regular. We recall that the odd-girth of a graph is the length of the shortest odd cycle in the graph, and that the odd-girth follows from the spectrum of the graph. The odd-girth theorem generalizes a result of Huang and Liu [32], who showed that every graph that is cospectral to a generalized Odd graph is distance-regular. In order to obtain our results we will, among others, make use of some results on so-called almost distance-regular graphs by Dalfó, Van Dam, Fiol, Garriga, and Gorissen [11]. An important ingredient of our work is an inequality that is inspired by the spectral excess theorem. This result by Fiol and Garriga [26] (for short proofs, see [15,25]) states that if for every vertex u, the number of vertices at distance d from u is the same as the socalled spectral excess (which can be expressed in terms of the spectrum), then the graph is distance-regular. This paper is organized as follows. In Section 2, we give some basic background information. Also, we recall by Theorem 2.4 a result that surveys when a graph that is cospectral with a distance-regular must be distance-regular itself. In Section 3 we present a few lemmas about properties of the preintersection numbers that are relevant for the proofs of our main results, which are derived in Section 4. In particular, in Section 4.1, an alternative formulation of the odd-girth theorem is presented; in Section 4.2, we prove distance-regularity for graphs with large girth; in Section 4.3, conditions on the preintersection numbers are used to prove distance-regularity. Finally, in Section 4.4, we apply the results from Section 4.3 to refine the results in Section 4.2 for graphs with large girth.

Background
In this section we recall some basic concepts, notation, and results on which our study is based. For more background on spectra of graphs, distance-regular graphs, and their characterizations, see [4,5,7,10,22,23,28]. Throughout this paper, G = (V, E) denotes a finite, simple, and connected graph with vertex set V , order n = |V |, size e = |E|, and diameter D. The set ('sphere') of vertices at distance i = 0, . . . , D from a given vertex u ∈ V is denoted by S i (u), and we let k i (u) = |S i (u)|. When the numbers k i (u) do not depend on the vertex u ∈ V , which is the case when the graph is distance-regular, we simply write k i . For a regular graph, we sometimes abbreviate the valency k 1 by k. Recall also that, for every i = 0, . . . , D, the distance matrix A i has entries (A i ) uv = 1 if the distance between u and v, denoted dist(u, v), is given by dist(u, v) = i, and (A i ) uv = 0 otherwise. Thus, A i is the adjacency matrix of the distance-i graph G i . In particular, A 0 = I is the identity matrix, A 1 = A is the adjacency matrix of G. Note that A 0 + · · · + A D = J , the all-1 matrix.
The spectrum of G is defined as the spectrum of A, i.e., where the distinct eigenvalues of A are ordered decreasingly: λ 0 > · · · > λ d , and the superscripts stand for their multiplicities m i = m(λ i ). Note that, since G is connected, m 0 = 1, and if G is regular then λ 0 = k. Throughout the paper, d will denote the number of distinct eigenvalues minus one.

Orthogonal polynomials and preintersection numbers
Orthogonal polynomials have been useful in the study of distance-regular graphs. Given a graph G with adjacency matrix A, and spectrum {λ m 0 0 , . . . , λ m d d }, we consider the scalar product where the second equation follows from standard properties of the trace. Within the vector space of real symmetric n × n matrices, we also use the common scalar product M , N = 1 n sum(M • N ), where '•' stands for the entrywise or Hadamard product, and sum(·) denotes the sum of the entries of the corresponding matrix. Note that p, q G = p(A), q(A) .
Fiol and Garriga [26] introduced the predistance polynomials p 0 , p 1 , . . . , p d as the unique sequence of orthogonal polynomials (so with dgr p i = i for i = 0, . . . , d) with respect to the scalar product (1) that are normalized in such a way that p i 2 G = p i (λ 0 ). Like every sequence of orthogonal polynomials, the predistance polynomials satisfy a three-term recurrence for certain coefficients α i , β i , and γ i , where β −1 = γ d+1 = 0, and p −1 and p d+1 are undetermined. For convenience, we also define the coefficients γ 0 = 0 and β d = 0.
We also consider the preintersection numbers ξ h ij , which are the Fourier coefficients of p i p j in terms of the basis {p h } 0≤h≤d , that is, Note that, in particular, the coefficients of the three-term recurrence (2) When G is distance-regular, the predistance polynomials become the distance polynomials, so that p i (A) = A i and p i (λ 0 ) = k i for i = 0, . . . , D; and the preintersection numbers become the intersection numbers p h ij = |S i (u) ∩ S j (v)|, where u and v are such that dist(u, v) = h. For an arbitrary graph and i, j, h ≤ D, we say that the intersection number p h ij is well-defined if the numbers p h ij (u, v) = |S i (u) ∩ S j (v)| are the same for all vertices u, v at distance h, and, in particular, we write We also consider the average

Partially distance-regular graphs
A graph G with diameter D is called m-partially distance-regular, for some m = 0, . . . , D, if its predistance polynomials satisfy p i (A) = A i for every i ≤ m (see Dalfó, Van Dam, Fiol, Garriga, and Gorissen [11]). In particular, every m-partially distance-regular with m ≥ 1 must be regular. This is because p 1 = (λ 0 /k)x and, hence, p 1 (A) = A implies k = λ 0 , a condition that is equivalent to G being regular (see e.g. Brouwer and Haemers [7]). As an alternative characterization, we have that G is m-partially distance-regular when the intersection numbers c i , a i , b i up to c m are well-defined, that is, the distance matrices satisfy the recurrence In this case, these intersection numbers are equal to the corresponding preintersection numbers γ i , α i , β i up to γ m . The two following results were derived in [11] by using both characterizations.
Lemma 2.2. Let G be a regular graph with girth g. Then G is m-partially distance-regular with m = (g − 1)/2 . Proposition 2.3. Let G be a graph with d + 1 distinct eigenvalues.
(ii) If G is bipartite and (d − 2)-partially distance-regular, then G is distance-regular.

Distance-regularity from cospectrality with a distance-regular graph
It is well-known that every regular graph G with d + 1 = 3 distinct eigenvalues is distanceregular (so, in this case, it is strongly regular). However, when d + 1 ≥ 4, only in some special cases it follows from the spectrum of G that it is distance-regular. The following theorem, given in the recent survey by Van Dam, Koolen, and Tanaka [22] (see also Van Dam and Haemers [18] and Brouwer and Haemers [7]), shows these cases. Note that one of the assumptions is that the graph is cospectral with a distance-regular graph.
Theorem 2.4. If Γ is a distance-regular graph with diameter D = d and girth g satisfying one of the properties (i)-(ix), then every graph G cospectral with Γ is also distance-regular and G has the same intersection numbers as Γ.

Some properties of the preintersection numbers
The main purpose of this section is to derive some properties of the predistance polynomials and preintersection numbers. We will make use of them in order to prove our main results in Section 4.
Lemma 3.1. For i = 0, . . . , d, the two highest terms of the predistance polynomial p i are as in the following expression: Proof. Use induction by using the three-term recurrence (2) and initial value p 0 = 1.
Note that if the graph is regular, then γ 1 = 1 and p 1 = x.
It is known that the intersection numbers a i , b i , and c i are nonnegative integers satisfying properties with precise combinatorial meanings (see, for instance, [4,5]). In contrast, this does not hold for the corresponding preintersection numbers α i , β i , and γ i , which in general are not necessarily integral. Nevertheless, the latter do share some of the properties of the former, as shown in Lemma 2.1 and in the following result.
Lemma 3.2. Let G be a graph with distinct eigenvalues λ 0 > · · · > λ d , and preintersection numbers α i , β i , and γ i . Then Thus, by Lemma 2.1(iii), we only need to prove the condition on the γ i 's. Moreover, by the interlacing property of orthogonal polynomials, we know that all the zeros of p i lie between λ d and λ 0 . Consequently, the leading coefficient ω i of p i must be positive, as lim x→∞ p i (x) = ∞. Thus, the conclusion is obtained since by Lemma 3.1, we have ω i = (γ 1 · · · γ i ) −1 for i = 1, . . . , d. To prove (ii) just use Lemma 2.1(v) and consider the trace of the recurrence matrix R.
In contrast with the above, we know that there are graphs such that λ 0 + · · · + λ d < 0 and, hence, by Lemma 3.2(ii), some of their preintersection numbers α i must be negative. An example is the cubic graph G with 12 vertices and d = 10 of Figure 1   Note that the α i 's sum up to −1, in accordance with Lemma 3.2(ii). (Here we should warn the reader that most of the eigenvalues and the entries of the table are not exact but rounded.) Note also that, contrarily to the case of the intersection numbers b i 's and c i 's, the β i 's and the γ i 's do not show a monotone behavior and, even more, γ 6 > λ 0 .
On the other hand, the given graph does not have triangles and α 1 = 0. This is not a coincidence: It follows from an inductive argument first used by Van Dam and Haemers [20] that the odd-girth (that is, the length of the shortest odd cycle) can be determined from the preintersection numbers as follows. Proof. Let us first assume that G has odd girth 2m + 1. Then tr A 2i+1 = 0 for i = 0, . . . , m − 1 and tr A 2m+1 = 0. Using this, it can be shown by induction (like in [20]) that α i = 0 for i < m and that the predistance polynomials p i are odd or even functions depending on whether i is odd or even, respectively, for i ≤ m. Moreover, since the polynomial xp 2 m is an odd function and has degree 2m + 1, so the leading term is the only one contributing to the trace.
Conversely, assume that the preintersection numbers satisfy α i = 0 for i = 0, . . . , m − 1 and α m = 0. Then again, by (2), the parity of the predistance polynomial p i (that is, it is an odd or even function) coincides with the parity of its index i for i = 0, . . . , m. Then, for any i < m we have that tr A 2i+1 = n A i , A i+1 = n x i , x i+1 G = 0, as the expressions of x i and x i+1 in terms of the basis p 0 , . . . , p m have polynomials with distinct parity. Thus, G has no odd cycles of length smaller than 2m + 1, and since α m = 0, it follows (from the first part of the proof) that the odd-girth is indeed 2m + 1.
The statement about bipartiteness follows from using parts of the above arguments.
Note that in general, the girth is not determined by the spectrum, but for regular graphs it is. In Corollary 4.10 we will make this explicit in terms of the preintersection numbers.

New quasi-spectral characterizations of distance-regular graphs
This section contains the main results of our work. As mentioned in the introduction, we give sufficient conditions for distance-regularity of a graph G, without requiring G to be cospectral with a distance-regular graph. We begin with an alternative formulation of the so-called odd-girth theorem [20].

The odd-girth theorem revisited
Theorem 2.4(iv) was generalized by Van Dam and Haemers [20] as the odd-girth theorem, which states that a graph G with d + 1 distinct eigenvalues and odd-girth 2d + 1 is distance-regular. By our Lemma 3.3, the condition on the odd-girth of G is equivalent to α 1 = · · · = α d−1 = 0, α d = 0, which corresponds to the condition a 1 = · · · = a d−1 = 0, a d = 0 of Theorem 2.4(iv). Note that Lee and Weng [34], and Van Dam and Fiol [16] showed that the odd-girth theorem is not restricted to regular graphs.
Before presenting an alternative formulation of the odd-girth theorem, recall that a generalized Odd graph is a distance-regular graph with diameter D and odd-girth 2D + 1. A well-know example is the Odd graph O k , whose vertices represent the (k − 1)-element subsets of a (2k − 1)-element set, where two vertices are adjacent if and only if their corresponding subsets are disjoint, see Biggs [4].
Theorem 4.1. Let G be a non-bipartite graph with d + 1 distinct eigenvalues.
with equality if and only if G is a distance-regular generalized Odd graph.
Of course, one of the cases (but certainly not the only one) where the hypothesis that α i ≥ 0 for i = 0, . . . , d − 1 holds, is when G is cospectral with a distance-regular graph. We recall however that the hypothesis is not satisfied in general, see the graph of Figure 1.
In contrast with the above, if G is bipartite, then γ d = −(λ 1 + · · · + λ d ), but in general we cannot conclude that G is distance-regular. For instance, a counterexample is the Hoffman graph [31], shown in Figure 2, which is cospectral with the distance-regular 4cube Q 4 and hence it is bipartite with d = 4 (α 0 = · · · = α 4 = 0). The Hoffman graph is not distance-regular however.

Distance-regularity from large girth
The first two cases of Theorem 2.4 can be generalized as follows.
Theorem 4.2. A regular graph G with girth g is distance-regular if any of the following condition holds: -partially distance-regular by Lemma 2.2, and the result follows from Proposition 2.3(i). The proof of (ii) is similar by using Proposition 2.3(ii).
We recall that the condition of being bipartite follows from the spectrum and also the girth of a regular graph is determined by the spectrum, so the assumptions in this result only depend on the spectrum of G.
As a consequence, and since a bipartite graph has girth g ≥ 4, we obtain the following known results (see, for instance, Abiad, Dalfó, and Fiol [1,2]). (i) If G has d + 1 = 4 distinct eigenvalues, then it is distance-regular, (ii) If G has d + 1 = 5 distinct eigenvalues and every pair of vertices at distance two has the same number of common neighbors, then it is distance-regular.
Proof. (i) This follows immediately from Theorem 4.2(ii). The condition on the number of common neighbors in (ii) implies that c 2 is well-defined and hence that G is 2-partially distance-regular. By Proposition 2.3(ii), it then follows that G is distance-regular.

Distance-regularity from the (pre)intersection numbers
In this section we show how the preintersection numbers can be used to prove distanceregularity. With this aim, we give some properties of the preintersection numbers of (m−1)-partially distance-regular graphs.  Proof. Note first that, since G is (m − 1)-partially distance-regular, all its intersections numbers up to c m−1 are well-defined. Then the following computation proves the first part of (i): The equalities β m−1 = k − c m−1 − α m−1 = b m−1 follow from the above, the regularity assumption, and Lemma 2.1(ii). Moreover, by counting in two ways the total number of edges between S m−1 (u) and S m (u) for all u ∈ V , see Figure 3(a), we get: Hence, whence the second equality for β m−1 = b m−1 in (i) follows. Here we remark that k m > 0 because m ≤ D, but the values of c m (u, v) are really only used for the case of a vertex v at distance m from a vertex u. We do not require that every vertex u has a vertex at distance m. Note also that k m−1 = p m−1 (λ 0 ).
Moreover, by (3), where we used (5) for the third equality, whereas for the fifth equality we used that and similarly that tr whence the result follows.
The following observation is the key to many of our results. It is motivated by the spectral excess theorem and we will use it to prove Proposition 4.6. From there, we will derive several spectral and quasi-spectral characterizations of distance-regularity.
where we used Lemma 2.1(iv). Then, by the Cauchy-Schwarz inequality, p 2 m (λ 0 ) ≤ p m (A) 2 A m 2 = p m (λ 0 )k m , and hence k m ≥ p m (λ 0 ). Furthermore, in the case of equality, p m (A) = αA m for some α ∈ R, and by taking norms we get that α = 1 since p m (λ 0 ) > 0. Now we are ready to give the following result, which generalizes some fundamental results by Van Dam and Haemers [17], and Van Dam, Haemers, Koolen, and Spence [21]. Proposition 4.6. Let G be a regular graph and let m ≤ D be a positive integer. Suppose that G is (m − 1)-partially distance-regular and any of the following conditions holds: where we also used Lemma 2.1(iii), see Figure 3(b). Now the conclusion follows from Proposition 4.5.
(ii) This is a simple consequence of (i) since, for every pair of vertices u, v at distance m, (iv) From Lemma 4.4(iii) and the hypothesis, we have that p m (λ 0 ) ≥ k m , and the result follows again from Proposition 4.5.
(v) From the hypothesis, we get c 2 m ≤ γ m c m , but from Lemma 4.4(iv), this must be an equality. Therefore, the intersection number c m is also well-defined and equal to γ m , which proves the result.
Since c 2 m ≥ (c m ) 2 , the result with condition (i) is a consequence of the result involving condition (iv). Also, observe that, because of Lemma 4.4(i), the proof of Proposition 4.6(v) also works if we change the hypothesis 'a m−1 is well-defined' to either 'a m−1 (u, v) ≤ α m−1 for every u, v at distance m − 1' or 'a m−1 (u, v) ≥ α m−1 for every u, v at distance m − 1'. The result also holds if we require that 'c m (u, v) ≥ γ m for every u, v at distance m', in which case we do not need the above hypotheses on a m−1 since then c m ≥ γ m and the result follows from Proposition 4.6(i).
As a consequence of Proposition 4.6(i), and since every regular graph is clearly 1-partially distance-regular with c 1 = γ 1 = 1, we have the following result.
From Theorem 4.7(i), it clearly follows that if G has the parameters c i well-defined and equal to γ i for i = 1, . . . , d − 1, then G is distance-regular. Note that it is not enough to assume only that the c i 's are well-defined. To illustrate this, we give an example of a non-distance-regular graph with well-defined k i and c i . Consider the strong product G of the cube Q 3 with the complete graph K 2 , shown in Figure 4. This graph is 7-regular with spectrum sp G = {7 1 , 3 3 , −1 11 , −5 1 }, it has diameter D = d = 3, and well-defined intersection numbers c 1 = 1, c 2 = 4, and c 3 = 6. However, it is not a distance-regular graph. (Note that G has preintersection numbers γ 1 = 1, γ 2 = 4.571 and γ 3 = 4.816.) Even more so, it has well-defined k 1 = 7, k 2 = 6, and k 3 = 2 (which is easily seen because G is vertex-transitive). In fact, only a 1 and b 1 are not well-defined. Similarly, if you take the Kronecker product of the adjacency matrix of a bipartite distanceregular graph with even diameter D with the all-one matrix J 2 , then the result is the adjacency matrix of a regular graph with diameter D = d and with well-defined k i and a i , but it is not distance-regular, since c 2 and b 2 are not well-defined.
These examples show that the combinatorics is not sufficient and some extra spectral information is required. This is in line with earlier results in the literature, where cospec-trality with a distance-regular graph, or feasible spectrum for a distance-regular graph, is required (see, for example, Haemers [30] or Van Dam and Haemers [17]).
Another consequence of Proposition 4.6 is the following result. It corresponds to the result of Van Dam and Haemers [17] stated in Theorem 2.4(v), and its bipartite counterpart. Recall that the preintersection numbers are determined by the spectrum, and that regularity of a graph is characterized by the condition that γ 1 = 1.
Theorem 4.8. Let G be a graph with d + 1 distinct eigenvalues.
Proof. (i) If D ≤ d−1, then apply Proposition 4.6(i) or (ii) recursively (using that c m ≥ 1 and c m−1 ≥ 1) to derive that G is D-partially distance-regular, that is, that G is distanceregular. If D = d, then it follows similarly that G is (d − 1)-partially distance-regular, and then it follows from Proposition 2.3(i) that G is distance-regular. The proof of (ii) is similar.
Moreover, Proposition 4.6(ii) also yields the following slight improvement of Proposition 2.3. Recall that 1-partial distance-regularity implies regularity.
Proposition 4.9. Let G be a graph with d + 1 distinct eigenvalues.
To conclude this subsection, we also give a characterization of the girth of a regular graph in terms of the preintersection numbers (cf. Lemma 3.3 for a similar characterization for the odd-girth). (ii) A regular graph has girth 2m if and only if α 0 = · · · = α m−1 = 0, γ 1 = · · · = γ m−1 = 1, and γ m > 1.
Proof. This follows from combining Lemma 3.3 and Proposition 4.6(ii) recursively.

Distance-regularity from large girth revisited
Our aim here is to give some improvements of the results in Section 4.2 for graphs with large girth. First, from Proposition 4.6(v), we obtain a refinement of the results in Theorems 2.4(iii) and 4.2.
Theorem 4.11. Let G be a regular graph with d + 1 distinct eigenvalues λ 0 > · · · > λ d and girth g ≥ 2d − 2. Then with equality if and only if G is distance-regular and either bipartite or a generalized Odd graph.
Proof. Note that, from the hypothesis on the girth, G is (d − 2)-partially distance-regular with c i = γ i = 1 and a i = α i = 0 for i = 1, . . . , d − 2 (Lemma 2.2 and Corollary 4.10). Moreover, since the Hoffman polynomial is n/π 0 (the first equality comes from the three-term recurrence (2)). Now, if we consider two vertices u, v at distance d − 1, then the Hoffman polynomial, satisfying H(A) = J , yields Hence, Now let us assume, contrary to (6), that γ d ≤ −(λ 1 + · · · + λ d ), and aim to prove equality. Then, using the fact that γ d > 0 (Lemma 3.2(i)), we have Consequently, from Proposition 4.6(v), G is (d − 1)-partially distance-regular, and by using Proposition 2.3(i), we conclude that G is distance-regular with c d−1 = γ d−1 . Then, equalities in (8) hold for all vertices u, v at distance d−1, and we are in the case of equality: Moreover, this holds if and only if (A d ) uv = 0 in (7), which means that there are no odd cycles of length smaller than 2d + 1, so a 0 = · · · = a d−1 = 0, and G is either bipartite or a generalized Odd graph. Conversely, when G is bipartite, we have γ d = c d = −λ d = λ 0 (the degree of G), and the condition (6) is tight. Moreover, when G is a generalized Odd graph, with odd-girth 2d + 1, Van Dam and Haemers [20] proved that α d = a d = λ 0 + · · · + λ d (this is also a consequence of Lemma 3.2(ii)), and equality in (6) follows again from α d + γ d = λ 0 (Lemma 2.1(ii)).
Note that, as a consequence of Theorem 4.11, the assumptions of Theorem 2.4(iii) seem to be quite strong.
An alternative reasoning that suggests (6) is the following. Since the odd-girth of G is at least 2d − 1, it follows by (4) that (6) is equivalent to α d−1 ≥ 0.
By using Proposition 4.6(i), we can also obtain some related results. With this aim, let a Let G be a regular graph with d + 1 distinct eigenvalues λ 0 > · · · > λ d and girth g ≥ 2d − 2.
with equality if and only if G is distance-regular, On the other hand, (7) and (4) imply that if u, v are two vertices at distance d − 1, then

Proof. Necessity in (i) and (ii) is clear since, when
Thus, by taking averages over all vertices u, v at distance d − 1, we have Now, for proving sufficiency in the case (i), let us assume that a (d) d−1 ≤ α d−1 γ d−1 , and aim to prove equality. Then by the hypothesis that α d−1 < γ d , we obtain that Then, by Proposition 4.6(i), G is (d − 1)-partially distance-regular, and the result follows from Proposition 2.3(i). The proof of sufficiency for the case (ii) is similar.
Another-putative-graph suggest that the graphs in this case need not be distanceregular. It is the first relation in a putative 3-class association scheme on 81 vertices, the parameters of which occur on top of p. 102 in the list of [14] (with the second relation being the Brouwer-Haemers graph). The spectrum is 30 }, and it follows that the (relevant) preintersection numbers are α 1 = 0 (so g ≥ 2d − 2), γ 2 = 13 9 , and α 2 = γ 3 = 99 13 . Thus, if a graph with this spectrum exists, then it will not be distance-regular. Now if you consider the graph in the association scheme, then for both types of vertices at distance 2 from a fixed vertex (the type depending on c 2 (x, y) being 1 or 2), you can count the number of walks of length 3 using the intersection numbers of the scheme, and indeed in both cases this number equals α 2 γ 2 = 11.
Here it is also worth noting that, under the conditions of the above proposition, the average number of walks a where we have used that (A d−1 ) uv = 0 when dist(u, v) ≥ d and, since a d−2 = 0, Note also that for a regular graph with girth g ≥ 2d − 2, one can derive nice formulas for the predistance polynomials. Indeed, from γ i = 1, α i = 0, β i = k − 1 for i = 0, . . . , d − 2, it follows by induction that for i = 0, . . . , d − 1. From this, one can also get p d , in particular that Then, by looking at the second term of the Hoffman polynomial (or p d + p d−1 ), we obtain (4) again.
In order to give a generalization of Proposition 4.12 we now first need to recall the concepts of local multiplicity and walk-regular graph. For i = 0, . . . , d, let E i be the (minimal ) idempotent of A that corresponds to the orthogonal projection onto the eigenspace corresponding to λ i . By analogy with the so-called local multiplicities, which correspond to the diagonal entries of the idempotents, Fiol, Garriga, and Yebra [27] defined the crossed (uv-)local multiplicities of the eigenvalue λ i , denoted by m uv (λ i ), as m uv (λ i ) = (E i ) uv , u, v ∈ V ; i = 0, . . . , d.
For regular graphs, E 0 = 1 n J and, hence, m uv (λ 0 ) = 1/n for every u, v ∈ V . The crossed local multiplicities allow us to express the number of walks of length between two vertices u, v in the following way: A graph G with diameter D is called h-punctually walk-regular, for some h = 0, . . . , D, when for every , the number of walks a ( ) uv is the same for every pair of vertices u, v at distance h. From the above expression it follows that this is equivalent to the crossed local multiplicities m uv (λ i ) being the same for every pair of vertices u, v at distance h (i.e., they only depend on i; see Dalfó, Van Dam, Fiol, Garriga, and Gorissen [11] for more details). Moreover, G is called m-walk-regular for some m ≤ D if it is h-punctually walk-regular for every h ≤ m (see Dalfó,Fiol,and Garriga [12]).
Proof. By considering the number of walks between two vertices u, v at distance d − 1, we obtain the following d equations: This can be seen as a determined system of d equations and d unknowns m uv (λ i ), i = 1, . . . , d, since its coefficient matrix is nonsingular. Indeed, if σ = λ 1 + · · · + λ d , then it follows from expanding the (Hoffmanlike) polynomial i =0 (x − λ i ) that λ d i = σλ d−1 i + g d−2 (λ i ) for some polynomial g d−2 of degree at most d − 2, for all i = 0. Hence, the determinant of the coefficient matrix is σ times the determinant of the Vandermonde matrix V , with entries (V ) ij = λ j−1 i for all i, j = 1, . . . , d.
As a consequence, the crossed local multiplicities m uv (λ i ) are the same for all vertices u, v at distance d − 1 and G is (d − 1)-punctually walk-regular. In particular, the number of walks a So c d−1 is well-defined and, since a d−2 and b d−2 = λ 0 −c d−2 −a d−2 are also well-defined, G is (d − 1)-partially distance-regular, and the result follows again from Proposition 2.3(i).
The above technique of computing the (crossed) local multiplicities through a system of equations has also been used to give a short proof of the odd-girth theorem (see Van Dam and Fiol [16]), and to prove that every pseudo-distance-regularized graph, which is a generalization of distance-regularized graphs in the sense of Godsil and Shawe-Taylor [29], is either distance-regular or distance-biregular (see Fiol [24]).