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 relationship between the diameter and the intersection number c 2 for a distance-regular graph

In this paper we will look at the relationship between the intersection number c ₂ and the diameter of a distance-regular graph. We also give some tools to show that a distance-regular graph with large c ₂ is bipartite, and a tool to show that if k _D is too small then the distance-regular graph has to be antipodal.     

The girth of a thin distance-regular graph

Let Γ be a distance-regular graph of diameterd≥3. For each vertexx of Γ, letT(x) denote the Terwilliger algebra for Γ with respect tox. An irreducibleT(x)-moduleW is said to bethin if dimE _i ^* (x)W≤1 for 0≤i≤d, whereE _i ^* (x) is theith dual idempotent for Γ with respect tox. The graph Γ isthin if for each vertexx of Γ, every irreducibleT(x)-module is thin. Aregular generalized quadrangle is a bipartite distance-regular graph with girth 8 and diameter 4. Our main results are as follows: Theorem. Let Γ=(X,R) be a distance-regular graph with diameter d≥3 and valency k≥3. Then the following are equivalent:

1. Γis a regular generalized quadrangle.
2. Γis thin and c ₃=1.

Corollary. Let Γ=(X,R) be a thin distance-regular graph with diameter d≥3 and valency k≥3. Then Γ has girth 3, 4, 6, or 8. Then girth of Γ is 8 exactly when Γ is a regular generalized quadrangle.     

An intersection graph of straight lines

G. Ehrlich, S. Even, and R.E. Tarjan conjectured that the graph obtained from a complete 3 partite graph K_4,4,4 by deleting the edges of four disjoint triangles is not the intersection graph of straight line segments in the plane. We show that it is.     

The local eigenvalues of a bipartite distance-regular graph

We consider a bipartite distance-regular graph $\Gamma$ with vertex set $X$, diameter $D\ge 4$, and valency $k\ge 3$. For $0\le i\le D$, let ${\Gamma }_i\left(x\right)$ denote the set of vertices in $X$ that are distance $i$ from vertex $x$. We assume there exist scalars $r,s,t\in \mathbb{R}$, not all zero, such that $r|{\Gamma }_1\left(x\right)\cap {\Gamma }_1\left(y\right)\cap {\Gamma }_2\left(z\right)|+s|{\Gamma }_2\left(x\right)\cap {\Gamma }_2\left(y\right)\cap {\Gamma }_1\left(z\right)|+t=0$ for all $x,y,z\in X$ with path-length distances $\partial (x,y)=2,\partial (x,z)=3,\partial (y,z)=3$. Fix $x\in X$, and let ${\Gamma }_2^2$ denote the graph with vertex set $\tilde{X}=\{y\in X\mid \partial (x,y)=2\}$ and edge set $\tilde{R}=\{yz\mid y,z\in \tilde{X},\partial (y,z)=2\}$. We show that the adjacency matrix of the local graph ${\Gamma }_2^2$ has at most four distinct eigenvalues. We are motivated by the fact that our assumption above holds if $\Gamma$ is $Q$-polynomial.     

The uniqueness of a distance-regular graph with intersection array $$\{32,27,8,1;1,4,27,32\}$$ and related results

It is known that, up to isomorphism, there is a unique distance-regular graph \(\Delta \) with intersection array \(\{32,27;1,12\}\) [equivalently, \(\Delta \) is the unique strongly regular graph with parameters (105, 32, 4, 12)]. Here we investigate the distance-regular antipodal covers of \(\Delta \). We show that, up to isomorphism, there is just one distance-regular antipodal triple cover of \(\Delta \) (a graph \(\hat{\Delta }\) discovered by the author over 20 years ago), proving that there is a unique distance-regular graph with intersection array \(\{32,27,8,1;1,4,27,32\}\). In the process, we confirm an unpublished result of Steve Linton that there is no distance-regular antipodal double cover of \(\Delta \), and so no distance-regular graph with intersection array \(\{32,27,6,1;1,6,27,32\}\). We also show there is no distance-regular antipodal 4-cover of \(\Delta \), and so no distance-regular graph with intersection array \(\{32,27,9,1;1,3,27,32\}\), and that there is no distance-regular antipodal 6-cover of \(\Delta \) that is a double cover of \(\hat{\Delta }\).     

Distance-regular subgraphs in a distance-regular graph, II

Let Γ be a distance-regular graph with r = l(1, a₁, b₁), a₁ > 0 and c_2r+1 = 1. We show the existence of a collinearity graph of a Moore geometry of diameter r + 1 as a subgraph in Γ. In particular, we show that r = 1.     

An inequality for the group chromatic number of a graph

We give an inequality for the group chromatic number of a graph as an extension of Brooks’ Theorem. Moreover, we obtain a structural theorem for graphs satisfying the equality and discuss applications of the theorem.     

The Terwilliger algebra of a distance-regular graph of negative type

Let Γ denote a distance-regular graph with diameter D?3. Assume Γ has classical parameters (D,b,α,β) with b<-1. Let X denote the vertex set of Γ and let A∈Mat_X(C) denote the adjacency matrix of Γ. Fix x∈X and let A^∗∈Mat_X(C) denote the corresponding dual adjacency matrix. Let T denote the subalgebra of Mat_X(C) generated by A,A^∗. We call T the Terwilliger algebra of Γ with respect to x. We show that up to isomorphism there exist exactly two irreducible T-modules with endpoint 1; their dimensions are D and 2D-2. For these T-modules we display a basis consisting of eigenvectors for A^∗, and for each basis we give the action of A.     

On automorphisms of a distance-regular graph with intersection array {39, 36, 1; 1, 2, 39}

Possible prime-order automorphisms and their fixed-point subgraphs are found for a hypothetical distance-regular graph with intersection array {39, 36, 1; 1, 2, 39}. It is shownthat graphs with intersection arrays {15, 12, 1; 1, 2, 15}, {35, 32, 1; 1, 2, 35}, and {39, 36, 1; 1, 2, 39} are not vertex-symmetric.     

On automorphisms of a distance-regular graph with intersection array {35, 32, 1; 1, 4, 35}

Prime divisors of orders of automorphisms and their fixed-point subgraphs are studied for a hypothetical distance-regular graph with intersection array {35, 32, 1; 1, 4, 35}. It is shown that there are no arc-transitive distance-regular graphs with intersection array {35, 32, 1; 1, 4, 35}.