Tails of Bipartite Distance-regular Graphs

Let Γ denote a bipartite distance-regular graph with diameterD  ≥  4 and valency k ≥  3. Let θ 0  > θ 1  >  >  θD denote the eigenvalues of Γ and let E₀, E₁, , E_Ddenote the associated primitive idempotents. Fix s(1  ≤  s ≤  D −  1 ) and abbreviate E: =  E_s. We say E is a tail whenever the entrywise product E   E is a linear combination of E₀, E and at most one other primitive idempotent of Γ. Letq_ij^{σi + 1 h} (0  ≤ h , i, j ≤  D) denote the Krein parameters of Γ and letΔ denote the undirected graph with vertices 0, 1, , D where two vertices i, j are adjacent whenever i ≠  =  j andq_ij^σi + 1s  ≠  =  0. We show E is a tail if and only if one of (i)–(iii) holds: (i) Δ is a path; (ii) Δ has two connected components, each of which is a path; (iii) D =  6 and Δ has two connected components, one of which is a path on four vertices and the other of which is a clique on three vertices.     

Bipartite Distance-regular Graphs, Part II

This is a continuation of “Bipartite Distance-regular Graphs, Part I”. We continue our study of the Terwilliger algebra T of a bipartite distance-regular graph. In this part we focus on the thin irreducible T-modules of endpoint 2 and on those distance-regular graphs for which every irreducible T-module of endpoint 2 is thin. Revised: June 2, 1997     

Bipartite Distance-regular Graphs, Part I

Let Γ=(X,E) denote a bipartite distance-regular graph with diameter D≥4, and fix a vertex x of Γ. The Terwilliger algebra T=T(x) is the subalgebra of Mat _X(C) generated by A, E ^* ₀, E ^* ₁,…,E ^* _D, where A denotes the adjacency matrix for Γ and E ^* _i denotes the projection onto the i ^TH subconstituent of Γ with respect to x. An irreducible T-module W is said to be thin whenever dimE ^* _i W≤1 for 0≤i≤Di. The endpoint of W is min{i|E ^* _i W≠0}. We determine the structure of the (unique) irreducible T-module of endpoint 0 in terms of the intersection numbers of Γ. We show that up to isomorphism there is a unique irreducible T-module of endpoint 1 and it is thin. We determine its structure in terms of the intersection numbers of Γ. We determine the structure of each thin irreducible T-module W of endpoint 2 in terms of the intersection numbers of Γ and an additional real parameter ψ=ψ(W), which we refer to as the type of W. We now assume each irreducible T-module of endpoint 2 is thin and obtain the following two-fold result. First, we show that the intersection numbers of Γ are determined by the diameter D of Γ and the set of ordered pairs

Nonexistence of some Antipodal Distance-regular Graphs of Diameter Four

We find an inequality involving the eigenvalues of a regular graph; equality holds if and only if the graph is strongly regular. We apply this inequality to the first subconstituents of a distance-regular graph and obtain a simple proof of the fundamental bound for distance-regular graphs, discovered by Juri i , Koolen and Terwilliger. Using this we show that for distance-regular graphs with certain intersection arrays, the first subconstituent graphs are strongly regular. From these results we prove the nonexistence of distance-regular graphs associated to 20 feasible intersection arrays from the book Distance-Regular Graphs by Brouwer, Cohen and Neumaier .     

The Distance-regular Graphs with Intersection Number and with an Eigenvalue

and with an eigenvalue . Received: October 2, 1995/Revised: Revised November 26, 1997     

基于交叉点排列的几类距离正则图的谱分布

基于距离正则图的交叉点排列,给出了三类距离正则图的谱分布,讨论了一维整数格Z的距离矩阵与第一类切比雪夫多项式之间的关系,体现出研究图的谱分布的量子概率技巧.     

Fitting Height and Character Degree Graphs

Given a group G, Γ(G) is the graph whose vertices are the primes that divide the degree of some irreducible character and two vertices p and q are joined by an edge if pq divides the degree of some irreducible character of G. By a definition of Lewis, a graph Γ has bounded Fitting height if the Fitting height of any solvable group G with Γ(G)=Γ is bounded (in terms of Γ). In this note, we prove that there exists a universal constant C such that if Γ has bounded Fitting height and Γ(G)=Γ then h(G)≤C. This solves a problem raised by Lewis. Research supported by the Spanish Ministerio de Educación y Ciencia, MTM2004-06067-C02-01 and MTM2004-04665, the FEDER and Programa Ramón y Cajal.     

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).     

Fitting Height and Diameter of Character Degree Graphs

Let a graph Γ have bounded Fitting height (i.e., there is a bound on the Fitting heights of those groups whose character degree graph is Γ) and G be any solvable group with character degree graph Γ and Fitting height h(G). We improve Moretò's bound by proving that if no vertex in Γ is adjacent to every other one, then h(G) ≤4, else h(G) ≤6. As a consequence, if a solvable group G has character degree graph with diameter 3, then h(G) ≤4. Moreover, G has at most one non-abelian normal Sylow subgroup in this case.     

Distance-regular Subgraphs in a Distance-regular Graph, VI

In this paper we give a sufficient condition for the existence of a strongly closed subgraph which is (c_q+a_q)-regular of diameterqcontaining a given pair of vertices at distanceqin a distance-regular graph. Moreover we show that a distance-regular graph withr = max {j| (c_j,a_j,b_j) = (c₁,a₁,b₁)} ,b_{q − 1}>b_qandc_q+r = 1 satisfies our sufficient condition.     

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 .     

Distance-regular digraphs of girth 4

It is shown that all possible parameters for distance-regular digraphs of girth 4 consist of two one-parameter families. The smallest non-trivial example in one family is constructed while in the other family it is shown not to exist.     

Distance-regular graphs without 4-claws

We determine the distance-regular graphs with diameter at least 3 and $c_2\ge 2$ but without induced $K_{1,4}$-subgraphs.     

On a Conjecture of Bannai and Ito: There are Finitely Many Distance-regular Graphs with Degree 5, 6 or 7

Bannai and Ito conjectured in a 1987 paper that there are finitely many distance-regular graphs with fixed degree that is greater than two. In a series of papers they showed that their conjecture held for distance-regular graphs with degrees 3 or 4. In this paper we prove that the Bannai–Ito conjecture holds for degrees 5–7.     

Distance-regular graphs admitting a perfect 1-code

In this paper, we study the problem that which of distance-regular graphs admit a perfect 1-code. Among other results, we characterize distance-regular line graphs which admit a perfect 1-code. Moreover, we characterize all known distance-regular graphs with small valency at most 4, the distance-regular graphs with known putative intersection arrays for valency 5, and all distance-regular graphs with girth 3 and valency 6 or 7 which admit a perfect 1-code.     

Some Interlacing Results for the Eigenvalues of Distance-regular graphs

In this paper we study the absolute values of non-trivial eigenvalues of a distance-regular graph and find that these usually have large absolute value. We also give a motivation concerning a conjecture of Bannai and Ito.     

Distance-regular Cayley graphs with least eigenvalue $$$$

We classify the distance-regular Cayley graphs with least eigenvalue \(-2\) and diameter at most three. Besides sporadic examples, these comprise of the lattice graphs, certain triangular graphs, and line graphs of incidence graphs of certain projective planes. In addition, we classify the possible connection sets for the lattice graphs and obtain some results on the structure of distance-regular Cayley line graphs of incidence graphs of generalized polygons.     

Distance-regular graphs and (α, β)-geometries

We study the relation between distance-regular graphs and (α, β)-geometries in two different ways. We give necessary and sufficient conditions for the neighbourhood geometry of a distance-regular graph to be an (α, β)-geometry, and describe some (classes of) examples. On the other hand, properties of certain regular two-graphs allow us to construct (0, α)-geometries on the corresponding Taylor graphs.     

The Local Structure of a Bipartite Distance-regular Graph

In this paper, we consider a bipartite distance-regular graph Γ = (X, E) with diameter d ≥ 3. We investigate the local structure ofΓ , focusing on those vertices with distance at most 2 from a given vertex x. To do this, we consider a subalgebra R = R(x) ofMat_{0307a0x.gif X}(C), where 0307a1x.gifX denotes the set of vertices in X at distance 2 from x. R is generated by matrices Ã, 0307a2x.gif J, and 0307a3x.gif D defined as follows. For all y, z 0307a4x.gif X, the (y,z )-entry of à is 1 if y, z are at distance 2, and 0 otherwise. The (y, z)-entry of 0307a5x.gif J equals 1, and the (y,z )-entry of 0307a6x.gif D equals the number of vertices of X adjacent to each ofx , y, and z. We show that R is commutative and semisimple, with dimension at least 2. We assume thatR is one of 2, 3, or 4, and explore the combinatorial implications of this. We are motivated by the fact that if Γ has a Q-polynomial structure, thenR ≤ 4.     

Distance-regular graphs of large diameter that are completely regular clique graphs

A connected graph is said to be a completely regular clique graph with parameters (s, c), \(s, c \in {\mathbb {N}}\), if there is a collection \(\mathcal {C}\) of completely regular cliques of size \(s+1\) such that every edge is contained in exactly c members of \(\mathcal {C}\). It is known that many families of distance-regular graphs are completely regular clique graphs. In this paper, we determine completely regular clique graph structures, i.e., the choices of \(\mathcal {C}\), of all known families of distance-regular graphs with unbounded diameter. In particular, we show that all distance-regular graphs in this category are completely regular clique graphs except the Doob graphs, the twisted Grassmann graphs and the Hermitean forms graphs. We also determine parameters (s, c); however, in a few cases we determine only s and give a bound on the value c. Our result is a generalization of a series of works by J. Hemmeter and others who determined distance-regular graphs in this category that are bipartite halves of bipartite distance-regular graphs.