On almost distance-regular graphs

Distance-regular graphs are a key concept in Algebraic Combinatorics and have given rise to several generalizations, such as association schemes. Motivated by spectral and other algebraic characterizations of distance-regular graphs, we study ‘almost distance-regular graphs’. We use this name informally for graphs that share some regularity properties that are related to distance in the graph. For example, a known characterization of a distance-regular graph is the invariance of the number of walks of given length between vertices at a given distance, while a graph is called walk-regular if the number of closed walks of given length rooted at any given vertex is a constant. One of the concepts studied here is a generalization of both distance-regularity and walk-regularity called m-walk-regularity. Another studied concept is that of m-partial distance-regularity or, informally, distance-regularity up to distance m. Using eigenvalues of graphs and the predistance polynomials, we discuss and relate these and other concepts of almost distance-regularity, such as their common generalization of (?,m)-walk-regularity. We introduce the concepts of punctual distance-regularity and punctual walk-regularity as a fundament upon which almost distance-regular graphs are built. We provide examples that are mostly taken from the Foster census, a collection of symmetric cubic graphs. Two problems are posed that are related to the question of when almost distance-regular becomes whole distance-regular. We also give several characterizations of punctually distance-regular graphs that are generalizations of the spectral excess theorem.     

Lattices generated by subspaces in d-bounded distance-regular graphs

Let Γ denote a d-bounded distance-regular graph with diameter d2. A regular strongly closed subgraph of Γ is said to be a subspace of Γ. Define the empty set to be the subspace with diameter -1 in Γ. For 0ii+sd-1, let denote the set of all subspaces in Γ with diameters i,i+1,…,i+s including Γ and . If we define the partial order on by ordinary inclusion (resp. reverse inclusion), then is a poset, denoted by (resp. ). In the present paper we show that both and are atomic lattices, and classify their geometricity.     

Triangle-free distance-regular graphs

Let Γ denote a distance-regular graph with diameter d≥3. By a parallelogram of length 3, we mean a 4-tuple xyzw consisting of vertices of Γ such that ∂(x,y)=∂(z,w)=1, ∂(x,z)=3, and ∂(x,w)=∂(y,w)=∂(y,z)=2, where ∂ denotes the path-length distance function. Assume that Γ has intersection numbers a ₁=0 and a ₂≠0. We prove that the following (i) and (ii) are equivalent. (i) Γ is Q-polynomial and contains no parallelograms of length 3; (ii) Γ has classical parameters (d,b,α,β) with b<−1. Furthermore, suppose that (i) and (ii) hold. We show that each of b(b+1)²(b+2)/c ₂, (b−2)(b−1)b(b+1)/(2+2b−c ₂) is an integer and that c ₂≤b(b+1). This upper bound for c ₂ is optimal, since the Hermitian forms graph Her₂(d) is a triangle-free distance-regular graph that satisfies c ₂=b(b+1). Work partially supported by the National Science Council of Taiwan, R.O.C.     

On bipartite distance-regular graphs with a strongly closed subgraph of diameter three

Let Γ denote a distance-regular graph with a strongly closed regular subgraph Y. Hosoya and Suzuki [R. Hosoya, H. Suzuki, Tight distance-regular graphs with respect to subsets, European J. Combin. 28 (2007) 61-74] showed an inequality for the second largest and least eigenvalues of Γ in the case Y is of diameter 2. In this paper, we study the case when Γ is bipartite and Y is of diameter 3, and obtain an inequality for the second largest eigenvalue of Γ. Moreover, we characterize the distance-regular graphs with a completely regular strongly closed subgraph H(3,2).     

A simple proof of the spectral excess theorem for distance-regular graphs

The spectral excess theorem provides a quasi-spectral characterization for a (regular) graph Γ with d+1 distinct eigenvalues to be distance-regular graph, in terms of the excess (number of vertices at distance d) of each of its vertices. The original approach, due to Fiol and Garriga in 1997, was obtained by using a local approach, so giving a characterization of the so-called pseudo-distance-regularity around a vertex. In this paper we present a new simple projection method based in a global point of view, and where the mean excess plays an essential role.     

Classification of subsets with minimal width and dual width in Grassmann, bilinear forms and dual polar graphs

Brouwer, Godsil, Koolen and Martin [Width and dual width of subsets in polynomial association schemes, J. Combin. Theory Ser. A 102 (2003) 255-271] introduced the width w and the dual width w^* of a subset in a distance-regular graph and in a cometric association scheme, respectively, and then derived lower bounds on these new parameters. For instance, subsets with the property w+w^*=d in a cometric distance-regular graph with diameter d attain these bounds. In this paper, we classify subsets with this property in Grassmann graphs, bilinear forms graphs and dual polar graphs. We use this information to establish the Erd?s-Ko-Rado theorem in full generality for the first two families of graphs.     

The distance-regular graphs such that all of its second largest local eigenvalues are at most one

In this paper, we classify distance regular graphs such that all of its second largest local eigenvalues are at most one. Also we discuss the consequences for the smallest eigenvalue of a distance-regular graph. These extend a result by the first author, who classified the distance-regular graphs with smallest eigenvalue .     

A Note on Thin P-Polynomial and Dual-Thin Q-Polynomial Symmetric Association Schemes

Let Y denote a d-class symmetric association scheme, with d 3. We show the following: If Y admits a P-polynomial structure with intersection numbers p _ij ^h and Y is 1-thin with respect to at least one vertex, then p _ll ^l =0 p _li ⁱ =0 1 i - 1. If Y admits a Q-polynomial structure with Krein parameters q _ij ^h , and Y is dual 1-thin with respect to at least one vertex, then q _ll ^l = 0 q _li ⁱ = 01 i d-1.     

Pseudo 1-homogeneous distance-regular graphs

Let Γ be a distance-regular graph of diameter d≥2 and a ₁≠0. Let θ be a real number. A pseudo cosine sequence for θ is a sequence of real numbers σ ₀,…,σ _d such that σ ₀=1 and c _i σ _i−1+a _i σ _i +b _i σ _i+1=θ σ _i for all i∈{0,…,d−1}. Furthermore, a pseudo primitive idempotent for θ is E _θ =s ∑ _i=0 ^d σ _i A _i , where s is any nonzero scalar. Let be the characteristic vector of a vertex v∈VΓ. For an edge xy of Γ and the characteristic vector w of the set of common neighbours of x and y, we say that the edge xy is tight with respect to θ whenever θ≠k and a nontrivial linear combination of vectors , and Ew is contained in . When an edge of Γ is tight with respect to two distinct real numbers, a parameterization with d+1 parameters of the members of the intersection array of Γ is given (using the pseudo cosines σ ₁,…,σ _d , and an auxiliary parameter ε). Let S be the set of all the vertices of Γ that are not at distance d from both vertices x and y that are adjacent. The graph Γ is pseudo 1-homogeneous with respect to xy whenever the distance partition of S corresponding to the distances from x and y is equitable in the subgraph induced on S. We show Γ is pseudo 1-homogeneous with respect to the edge xy if and only if the edge xy is tight with respect to two distinct real numbers. Finally, let us fix a vertex x of Γ. Then the graph Γ is pseudo 1-homogeneous with respect to any edge xy, and the local graph of x is connected if and only if there is the above parameterization with d+1 parameters σ ₁,…,σ _d ,ε and the local graph of x is strongly regular with nontrivial eigenvalues a ₁ σ/(1+σ) and (σ ₂−1)/(σ−σ ₂).     

A family of weakly distance-regular digraphs of girth 2

A family of commutative weakly distance-regular digraphs of girth 2 was classified in [K. Wang, Commutative weakly distance-regular digraphs of girth 2, European J. Combin. 25 (2004) 363-375]. In this paper, we classify this family of digraphs without the assumption of commutativity.     

The Displacement and Split Decompositions for a Q-Polynomial Distance-regular Graph

Let denote a Q-polynomial distance-regular graph with diameter at least three and standard module V. We introduce two direct sum decompositions of V. We call these the displacement decomposition for and the split decomposition for . We describe how these decompositions are related.     

Finite Euclidean graphs and Ramanujan graphs

We consider finite analogues of Euclidean graphs in a more general setting than that considered in [A. Medrano, P. Myers, H.M. Stark, A. Terras, Finite analogues of Euclidean space, J. Comput. Appl. Math. 68 (1996) 221-238] and we obtain many new examples of Ramanujan graphs. In order to prove these results, we use the previous work of [W.M. Kwok, Character tables of association schemes of affine type, European J. Combin. 13 (1992) 167-185] calculating the character tables of certain association schemes of affine type. A key observation is that we can obtain better estimates for the ordinary Kloosterman sum K(a,b;q). In particular, we always achieve , and in many (but not all) of the cases, instead of the well known . Also, we use the ideas of controlling association schemes, and the Ennola type dualities, in our previous work on the character tables of commutative association schemes. The method in this paper will be used to construct many more new examples of families of Ramanujan graphs in the subsequent paper.     

Antipodal distance-regular graphs of diameter four and five

An antipodal distance-regular graph of diameter four or five is a covering graph of a connected strongly regular graph. We give existence conditions for these graphs and show for some types of strongly regular graphs that no nontrivial covers exist. © 1999 John Wiley & Sons, Inc. J Combin Designs 7: 69–77, 1999     

An inequality involving the second largest and smallest eigenvalue of a distance-regular graph

For a distance-regular graph with second largest eigenvalue (resp., smallest eigenvalue) θ₁ (resp., θ_D) we show that (θ₁+1)(θ_D+1)?-b₁ holds, where equality only holds when the diameter equals two. Using this inequality we study distance-regular graphs with fixed second largest eigenvalue.     

A class of amply regular graphs related to the subconstituents of a dual polar graph

The connected components of the induced graphs on each subconstituent of the dual polar graph of the odd dimensional orthogonal spaces over a finite field are shown to be amply regular. The connected components of the graphs on the second and third subconstituents are shown to be distance-regular by elementary methods.     

Theorems of Erd?s-Ko-Rado type in polar spaces

We consider Erd?s-Ko-Rado sets of generators in classical finite polar spaces. These are sets of generators that all intersect non-trivially. We characterize the Erd?s-Ko-Rado sets of generators of maximum size in all polar spaces, except for H(4n+1,q²) with n?2.     

On the primitive idempotents of distance-regular graphs

Let Γ denote a distance-regular graph with diameter d3. Let E, F denote nontrivial primitive idempotents of Γ such that F corresponds to the second largest or the least eigenvalue. We investigate the situation that there exists a primitive idempotent H of Γ such that EF is a linear combination of F and H. Our main purpose is to obtain the inequalities involving the cosines of E, and to show that equality is closely related to Γ being Q-polynomial with respect to E. This generalizes a result of Lang on bipartite graphs and a result of Pascasio on tight graphs.     

Using equality in the Krein conditions to prove nonexistence of certain distance-regular graphs

We prove the nonexistence of a distance-regular graph with intersection array {74,54,15;1,9,60} and of distance-regular graphs with intersection arrays

{4r³+8r²+6r+1,2r(r+1)(2r+1),2r²+2r+1;1,2r(r+1),(2r+1)(2r²+2r+1)}