Distance-Regular Graphs with Strongly Regular Subconstituents

In [3] Cameron et al. classified strongly regular graphs with strongly regular subconstituents. Here we prove a theorem which implies that distance-regular graphs with strongly regular subconstituents are precisely the Taylor graphs and graphs with a ₁ = 0 and a _i {0,1} for i = 2,...,d.     

Distance-Regular Graphs of Valency 6 and a1 = 1

We give a complete classification of distance-regular graphs of valency 6 and a₁ = 1.     

Tight Distance-Regular Graphs

We consider a distance-regular graph with diameter d 3 and eigenvalues k = ₀ > ₁ > ... > _d . We show the intersection numbers a ₁, b ₁ satisfy

A Characterization of Distance-Regular Graphs with Diameter Three

We characterize the distance-regular graphs with diameter three by giving an expression for the number of vertices at distance two from each given vertex, in terms of the spectrum of the graph.     

The Parameters of Bipartite Q-polynomial Distance-Regular Graphs

Let denote a bipartite distance-regular graph with diameter D 3 and valency k 3. Suppose ₀, ₁, ..., _D is a Q-polynomial ordering of the eigenvalues of . This sequence is known to satisfy the recurrence _{i – 1} – _i + _{i + 1} = 0 (0 > i > D), for some real scalar . Let q denote a complex scalar such that q + q ^–1 = . Bannai and Ito have conjectured that q is real if the diameter D is sufficiently large.We settle this conjecture in the bipartite case by showing that q is real if the diameter D 4. Moreover, if D = 3, then q is not real if and only if ₁ is the second largest eigenvalue and the pair (, k) is one of the following: (1, 3), (1, 4), (1, 5), (1, 6), (2, 4), or (2, 5). We observe that each of these pairs has a unique realization by a known bipartite distance-regular graph of diameter 3.     

On Subgraphs in Distance-Regular Graphs

Terwilliger [15] has given the diameter bound d (s – 1)(k – 1) + 1 for distance-regular graphs with girth 2s and valency k. We show that the only distance-regular graphs with even girth which reach this bound are the hypercubes and the doubled Odd graphs. Also we improve this bound for bipartite distance-regular graphs. Weichsel [17] conjectures that the only distance-regular subgraphs of a hypercube are the even polygons, the hypercubes and the doubled Odd graphs and proves this in the case of girth 4. We show that the only distance-regular subgraphs of a hypercube with girth 6 are the doubled Odd graphs. If the girth is equal to 8, then its valency is at most 12.     

The Terwilliger Algebra Associated with a Set of Vertices in a Distance-Regular Graph

Let Γ be a distance-regular graph of diameter D. Let X denote the vertex set of Γ and let Y be a nonempty subset of X. We define an algebra τ = τ(Y). This algebra is finite dimensional and semisimple. If Y consists of a single vertex then τ is the corresponding subconstituent algebra defined by P. Terwilliger. We investigate the irreducible τ-modules. We define endpoints and thin condition on irreducible τ-modules as a generalization of the case when Y consists of a single vertex. We determine when an irreducible module is thin. When the module is generated by the characteristic vector of Y, it is thin if and only if Y is a completely regular code of Γ. By considering a suitable subset Y, every irreducible τ(x)-module of endpoint i can be regarded as an irreducible τ(Y)-module of endpoint 0.This research was partially supported by the Grant-in-Aid for Scientific Research (No. 12640039), Japan Society of the Promotion of Science. A part of the research was done when the author was visiting the Ohio State University.     

On Distance-Regular Graphs with Height Two

Let be a distance-regular graph with diameter at least three and height h = 2, where . Suppose that for every in and in _d(), the induced subgraph on _d() ₂() is a clique. Then is isomorphic to the Johnson graph J(8, 3).     

On Distance-Regular Graphs with Height Two, II

Let be a distance-regular graph with diameter and height , where . Suppose that for every in and every in , the induced subgraph on is isomorphic to a complete multipartite graph with . Then and is isomorphic to the Johnson graph .     

An Inequality Involving the Local Eigenvalues of a Distance-Regular Graph

Let denote a distance-regular graph with diameter D 3, valency k, and intersection numbers a _i, b _i, c _i. Let X denote the vertex set of and fix x X. Let denote the vertex-subgraph of induced on the set of vertices in X adjacent X. Observe has k vertices and is regular with valency a ₁. Let _{1 2} ··· _k denote the eigenvalues of and observe ₁ = a ₁. Let denote the set of distinct scalars among ₂, ₃, ..., _k . For let mult denote the number of times appears among ₂, ₃,..., _k . Let denote an indeterminate, and let p ₀, p₁, ...,p _D denote the polynomials in [] satisfying p ₀ = 1 andp _i = c _i+1 p _i+1 + (a _i – c _i+1 + c _i)p _i + b _i p _i–1 (0 i D – 1),where p _–1 = 0. We show where we abbreviate = –1 – b ₁(1+)^–1. Concerning the case of equality we obtain the following result. Let T = T(x) denote the subalgebra of Mat _X ( ) generated by A, E*₀, E*₁, ..., E* _D , where A denotes the adjacency matrix of and E* _i denotes the projection onto the ith subconstituent of with respect to X. T is called the subconstituent algebra or the Terwilliger algebra. An irreducible T-module W is said to be thin whenever dimE* _i W 1 for 0 i D. By the endpoint of W we mean min{i|E* _i W 0}. We show the following are equivalent: (i) Equality holds in the above inequality for 1 i D – 1; (ii) Equality holds in the above inequality for i = D – 1; (iii) Every irreducible T-module with endpoint 1 is thin.     

Distance-Regular Graphs Related to the Quantum Enveloping Algebra of sl(2)

We investigate a connection between distance-regular graphs and U _q(sl(2)), the quantum universal enveloping algebra of the Lie algebra sl(2). Let be a distance-regular graph with diameter d 3 and valency k 3, and assume is not isomorphic to the d-cube. Fix a vertex x of , and let (x) denote the Terwilliger algebra of with respect to x. Fix any complex number q {0, 1, –1}. Then is generated by certain matrices satisfying the defining relations of U _q(sl(2)) if and only if is bipartite and 2-homogeneous.     

Distance-Regular Graphs with c i = b d-i and Antipodal Double Covers

Let be a distance-regular graph of diameter d and valency k > 2. Suppose there exists an integer s with d 2s such that c _i = b _d-i for all 1 i s. Then is an antipodal double cover.     

Uniformly Packed Codes and More Distance Regular Graphs from Crooked Functions

Let V and W be n-dimensional vector spaces over GF(2). A function Q : V W is called crooked (a notion introduced by Bending and Fon-Der-Flaass) if it satisfies the following three properties:

On the p-Ranks of the Adjacency Matrices of Distance-Regular Graphs

Let be a distance-regular graph with adjacency matrix A. Let I be the identity matrix and J the all-1 matrix. Let p be a prime. We study the p-rank of the matrices A + bJ – cI for integral b, c and the p-rank of corresponding matrices of graphs cospectral with .Using the minimal polynomial of A and the theory of Smith normal forms we first determine which p-ranks of A follow directly from the spectrum and which, in general, do not. For the p-ranks that are not determined by the spectrum (the so-called relevant p-ranks) of A the actual structure of the graph can play a rôle, which means that these p-ranks can be used to distinguish between cospectral graphs.We study the relevant p-ranks for some classes of distance-regular graphs and try to characterize distance-regular graphs by their spectrum and some relevant p-rank.     

A Distance-Regular Graph with Strongly Closed Subgraphs

Let be a distance-regular graph of diameter d, valency k and r := maxi | (c _i,b _i) = (c ₁,b ₁). Let q be an integer with r + 1 q d – 1.In this paper we prove the following results: Theorem 1 Suppose for any pair of vertices at distance q there exists a strongly closed subgraph of diameter q containing them. Then for any integer i with 1 i q and for any pair of vertices at distance i there exists a strongly closed subgraph of diameter i containing them. Theorem 2 If r 2, then c _2r+3 1.As a corollary of Theorem 2 we have d k ²(r + 1) if r 2.     

Leaves in Representation Diagrams of Bipartite Distance-Regular Graphs

Let denote a bipartite distance-regular graph with diameter D 3 and valency k 3. Let ₀ > ₁ ··· > _D denote the eigenvalues of and let q ^h _ij (0 h, i, j D) denote the Krein parameters of . Pick an integer h (1 h D – 1). The representation diagram = _h is an undirected graph with vertices 0,1,...,D. For 0 i, j D, vertices i, j are adjacent in whenever i j and q ^h _ij 0. It turns out that in , the vertex 0 is adjacent to h and no other vertices. Similarly, the vertex D is adjacent to D – h and no other vertices. We call 0, D the trivial vertices of . Let l denote a vertex of . It turns out that l is adjacent to at least one vertex of . We say l is a leaf whenever l is adjacent to exactly one vertex of . We show has a nontrivial leaf if and only if is the disjoint union of two paths.     

A New Distance-Regular Graph Associated to the Mathieu Group M 10

We construct a bipartite distance-regular graph with intersection array {45, 44, 36, 5; 1, 9, 40, 45} and automorphism group 3⁵ :(2 ×M₁₀) (acting edge-transitively) and discuss its relation to previously known combinatorial structures.     

There are Finitely Many Triangle-Free Distance-Regular Graphs with Degree 8, 9 or 10

In this paper we prove that there are finitely many triangle-free distance-regular graphs with degree 8, 9 or 10.     

Homogeneity of a Distance-Regular Graph Which Supports a Spin Model

A spin model is a square matrix that encodes the basic data for a statistical mechanical construction of link invariants due to V.F.R. Jones. Every spin model W is contained in a canonical Bose-Mesner algebra (W). In this paper we study the distance-regular graphs whose Bose-Mesner algebra satisfies W (W). Suppose W has at least three distinct entries. We show that is 1-homogeneous and that the first and the last subconstituents of are strongly regular and distance-regular, respectively.