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.     

Two distance-regular graphs

We construct two families of distance-regular graphs, namely the subgraph of the dual polar graph of type B ₃(q) induced on the vertices far from a fixed point, and the subgraph of the dual polar graph of type D ₄(q) induced on the vertices far from a fixed edge. The latter is the extended bipartite double of the former.     

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.     

Imprimitive symmetric graphs with cyclic blocks

Let Γ be a graph admitting an arc-transitive subgroup G of automorphisms that leaves invariant a vertex partition with parts of size v≥3. In this paper we study such graphs where: for connected by some edge of Γ, exactly two vertices of B lie on no edge with a vertex of C; and as C runs over all parts of connected to B these vertex pairs (ignoring multiplicities) form a cycle. We prove that this occurs if and only if v=3 or 4, and moreover we give three geometric or group theoretic constructions of infinite families of such graphs.     

Restrictions on classical distance-regular graphs

Let \(\varGamma \) be a distance-regular graph with diameter \(d \ge 2\). It is said to have classical parameters \((d, b, \alpha , \beta )\) when its intersection array \(\{b_0,b_1,\dots ,b_{d-1};c_1,c_2,\dots ,c_d\}\) satisfies

$$\begin{aligned} b_i= & {} ([d]_b - [i]_b)(\beta - \alpha [i]_b) \qquad \text {and} \qquad c_{i+1} = [i+1]_b (1 + \alpha [i]_b)\\&\quad (0 \le i \le d-1), \end{aligned}$$

where \([i]_b := 1 + b + \cdots + b^{i-1}\). Apart from the well-known families, there are many sets of classical parameters for which the existence of a corresponding graph is still open. It turns out that in most such cases we have either \(\alpha = b-1\) or \(\alpha = b\). For these two cases, we derive bounds on the parameter \(\beta \), which give us complete classifications when \(b = -2\). Distance-regular graphs with classical parameters are antipodal iff \(b=1\) and \(\beta =1+\alpha [d-1]_b\). If we drop the condition \(b=1\), it turns out that one obtains either bipartite or tight graphs. For the latter graphs, we find closed formulas for the parameters of the CAB partitions and the distance partition corresponding to an edge. Finally, we find a two-parameter family of feasible intersection arrays for tight distance-regular graphs with classical parameters \((d,b,b-1,b^{d-1})\) (primitive iff \(b \ne 1\)) and apply our results to show that it is realized only by d-cubes (\(b = 1\)).

     

On automorphisms of distance-regular graphs

In this paper, we present a survey of results on automorphisms of distance-regular graphs obtained at the department of algebra and topology of IMM UB RAS in the last five years. Also, we explain the Higman method of application of the character theory to the investigation of automorphisms of distance-regular graphs.     

Graphs cospectral with distance-regular graphs

We determine all graphs with the spectrum of a distance-regular graph with at most 30 vertices (except possibly for the Taylor graph on 28 vertices)     

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)/(σ−σ ₂).     

On 3-chromatic distance-regular graphs

We give some necessary conditions for a graph to be 3-chromatic in terms of the spectrum of the adjacency matrix. For all known distance-regular graphs it is determined whether they are 3-chromatic. A start is made with the classification of 3-chromatic distance-regular graphs, and it is shown that such graphs, if not complete 3-partite, must have λ ≤ 1.     

Distance-biregular graphs with 2-valent vertices and distance-regular line graphs

A graph G is called distance-regularized if each vertex of G admits an intersection array. It is known that every distance-regularized graph is either distance-regular (DR) or distance-biregular (DBR). Note that DBR means that the graph is bipartite and the vertices in the same color class have the same intersection array. A (k, g)-graph is a k-regular graph with girth g and with the minimum possible number of vertices consistent with these properties. Biggs proved that, if the line graph L(G) is distance-transitive, then G is either K_1,n or a (k, g)-graph. This result is generalized to DR graphs by showing that the following are equivalent: (1) L(G) is DR and G ≠ K_1,n for n ≥ 2, (2) G and L(G) are both DR, (3) subdivision graph S(G) is DBR, and (4) G is a (k, g)-graph. This result is used to show that a graph S is a DBR graph with 2-valent vertices iff S = K_2,′ or S is the subdivision graph of a (k, g)-graph. Let G⁽²⁾ be the graph with vertex set that of G and two vertices adjacent if at distance two in G. It is shown that for a DBR graph G, G⁽²⁾ is two DR graphs. It is proved that a DR graph H without triangles can be obtained as a component of G⁽²⁾ if and only if it is a (k, g)-graph with g ≥ 4.     

Bipartite Q-polynomial distance-regular graphs and uniform posets

Let Γ denote a bipartite distance-regular graph with vertex set X and diameter D≥3. Fix x∈X and let L (resp., R) denote the corresponding lowering (resp., raising) matrix. We show that each Q-polynomial structure for Γ yields a certain linear dependency among RL ², LRL, L ² R, L. Define a partial order ≤ on X as follows. For y,z∈X let y≤z whenever ?(x,y)+?(y,z)=?(x,z), where ? denotes path-length distance. We determine whether the above linear dependency gives this poset a uniform or strongly uniform structure. We show that except for one special case a uniform structure is attained, and except for three special cases a strongly uniform structure is attained.     

Pathological projective planes: Associate affine planes

In [7] the author showed the existence of projective plane pathological with respect to the collineation groups of its sub and quotient planes. Similar pathologies are obtainable with respect to collineation groups of associated affine planes. (i.e. the affine planes obtained by distinguishing a line as the line at infinity) as expressable in the following theorem.     

Distance-regularised graphs are distance-regular or distance-biregular

One problem with the theory of distance-regular graphs is that it does not apply directly to the graphs of generalised polygons. In this paper we overcome this difficulty by introducing the class of distance-regularised graphs, a natural common generalisation. These graphs are shown to either be distance-regular or fall into a family of bipartite graphs called distance-biregular. This family includes the generalised polygons and other interesting graphs. Despite this increased generality we are also able to extend much of the basic theory of distance-regular graphs to our wider class of graphs.