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.     

Extremal 1-codes in distance-regular graphs of diameter 3

We study 1-codes in distance-regular graphs of diameter 3 that achieve three different bounds. We show that the intersection array of a distance-regular graph containing such a code has the form $${\{a(p+1), cp, a+1; 1, c, a p\}\quad{\rm or}\quad\{a(p+1), (a+1)p,c; 1, c, a p\}}$$ for c =? c ₂,?a =? a ₃ and ${p = p_{33}^3}$ . These two families contain 10?+?15 known feasible intersection arrays out of which four are uniquely realized by the Sylvester graph, the Hamming graph H(3, 3), the Doro graph and the Johnson graph J(9, 3), but not all members of these two families are feasible. We construct four new one-parameter infinite subfamilies of feasible intersection arrays, two of which have a nontrivial vanishing Krein parameter: $${\{(2r^2-1)(2r+1), 4r(r^2-1), 2r^2; 1, 2(r^2-1), r(4r^2-2)\}}$$ and $${\{2r^2(2r+1), (2r-1)(2r^2+r+1), 2r^2; 1, 2r^2, r(4r^2-1)\}}$$ for r > 1 (the second family actually generalizes to a two-parameter family with the same property). Using this information we calculate some triple intersection numbers for these two families to show that they must contain the desired code. Finally, we use some additional combinatorial arguments to prove nonexistence of distance-regular graphs with such intersection arrays.     

Feasibility conditions for the existence of walk-regular graphs

A graph X is walk-regular if the vertex-deleted subgraphs of X all have the same characteristic polynomial. Examples of such graphs are vertex-transitive graphs and distance-regular graphs. We show that the usual feasibility conditions for the existence of a distance-regular graph with a given intersection array can be extended so that they apply to walk-regular graphs. Despite the greater generality, our proofs are more elementary than those usually given for distance-regular graphs. An application to the computation of vertex-transitive graphs is described.     

Completely regular clique graphs

Let Γ=(X,R) be a connected graph. Then Γ is said to be a completely regular clique graph of parameters (s,c) with s≥1 and c≥1, 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}\) . In this paper, we show that the parameters of \(C\in\mathcal{C}\) as a completely regular code do not depend on \(C\in\mathcal{C}\) . As a by-product we have that all completely regular clique graphs are distance-regular whenever \(\mathcal {C}\) consists of edges. We investigate the case when Γ is distance-regular, and show that Γ is a completely regular clique graph if and only if it is a bipartite half of a distance-semiregular graph.     

Amply regular graphs and block designs

We study the amply regular diameter d graphs Γ such that for some vertex a the set of vertices at distance d from a is the set of points of a 2-design whose set of blocks consists of the intersections of the neighborhoods of points with the set of vertices at distance d-1 from a. We prove that the subgraph induced by the set of points is a clique, a coclique, or a strongly regular diameter 2 graph. For diameter 3 graphs we establish that this construction is a 2-design for each vertex a if and only if the graph is distance-regular and for each vertex a the subgraph Γ₃(a) is a clique, a coclique, or a strongly regular graph. We obtain the list of admissible parameters for designs and diameter 3 graphs under the assumption that the subgraph induced by the set of points is a Seidel graph. We show that some of the parameters found cannot correspond to distance-regular graphs.     

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.     

Geometric aspects of 2-walk-regular graphs

A t-walk-regular graph is a graph for which the number of walks of given length between two vertices depends only on the distance between these two vertices, as long as this distance is at most t. Such graphs generalize distance-regular graphs and t-arc-transitive graphs. In this paper, we will focus on 1- and in particular 2-walk-regular graphs, and study analogues of certain results that are important for distance-regular graphs. We will generalize Delsarte?s clique bound to 1-walk-regular graphs, Godsil?s multiplicity bound and Terwilliger?s analysis of the local structure to 2-walk-regular graphs. We will show that 2-walk-regular graphs have a much richer combinatorial structure than 1-walk-regular graphs, for example by proving that there are finitely many non-geometric 2-walk-regular graphs with given smallest eigenvalue and given diameter (a geometric graph is the point graph of a special partial linear space); a result that is analogous to a result on distance-regular graphs. Such a result does not hold for 1-walk-regular graphs, as our construction methods will show.     

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.     

Delsarte Set Graphs with Small c 2

Let Γ be a Delsarte set graph with an intersection number c ₂ (i.e., a distance-regular graph with a set ${\mathcal{C}}Let Γ be a Delsarte set graph with an intersection number c ₂ (i.e., a distance-regular graph with a set C{\mathcal{C}} of Delsarte cliques such that each edge lies in a positive constant number n_C{n_{\mathcal{C}}} of Delsarte cliques in C{\mathcal{C}}). We showed in Bang et al. (J Combin 28:501–506, 2007) that if ψ ₁ > 1 then c ₂ ≥ 2 ψ ₁ where y₁:=|G₁(x)?C |{\psi_1:=|\Gamma_1(x)\cap C |} for x ? V(G){x\in V(\Gamma)} and C a Delsarte clique satisfying d(x, C) = 1. In this paper, we classify Γ with the case c ₂ = 2ψ ₁ > 2. As a consequence of this result, we show that if c ₂ ≤ 5 and ψ ₁ > 1 then Γ is either a Johnson graph or a folded Johnson graph [`(J)](4s,2s){\overline{J}(4s,2s)} with s ≥ 3.     

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.     

Distance-regular graphs with girth 3 or 4: I

We study the structure of a distance-regular graph Γ with girth 3 or 4. First, we find some relationships among the intersection numbers of Γ when Γ contains a cycle {u₁, u₂, u₃, u₄} with ?(u₁, u₃) = ?(u₂, u₄) = 2. These relationships imply the diameter d, valency k, and intersection numbers a₁ and c_d of Γ are related by $\text{d ≤}\text{(k + c}{}_{\mathrm{d}}\text{)}\text{(a}{}_1\text{+ 2)}$. Next, we show subgraphs induced by vertex neighbourhoods in distance-regular graphs where cycles mentioned above do not exist are related to certain strongly regular graphs.     

On the connectedness of the complement of a ball in distance-regular graphs

An important property of strongly regular graphs is that the second subconstituent of any primitive strongly regular graph is always connected. Brouwer asked to what extent this statement can be generalized to distance-regular graphs. In this paper, we show that if γ is any vertex of a distance-regular graph Γ and t is the index where the standard sequence corresponding to the second largest eigenvalue of Γ changes sign, then the subgraph induced by the vertices at distance at least t from γ, is connected.     

Spectral Characterizations of Some Distance-Regular Graphs

When can one see from the spectrum of a graph whether it is distance-regular or not? We give some new results for when this is the case. As a consequence we find (among others) that the following distance-regular graphs are uniquely determined by their spectrum: The collinearity graphs of the generalized octagons of order (2,1), (3,1) and (4,1), the Biggs-Smith graph, the M ₂₂ graph, and the coset graphs of the doubly truncated binary Golay code and the extended ternary Golay code.     

Antipodal graphs of diameter three

Distance-regular graphs of diameter three are of three (almost distinct) kinds: primitive, bipartite, and antipodal. An antipodal graph of diameter three is just an r-fold covering of a complete graph K_k+1 for some r?k. Its intersection array and spectrum are determined by the parameters r, k together with the number c of 2-arcs joining any two vertices at distance two. Most such graphs have girth three. In this note we consider antipodal distance-regular graphs of diameter three and girth ? 4. If r=2, then the only graphs are “K_{k+1, k+1} minus a 1-factor.” We therefore assume r?3. The graphs with c=1 necessarily have r=k and were classified in lsqb3rsqb. We prove the inequality $\text{r?2>c}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}$ (Theorem 2), list the feasible parameter sets when c=2 or 3 (Corollary 1), and conclude that every 3-fold or 4-fold antipodal covering of a complete graph has girth three (Corollary 2).     

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.     

Almost 2-Homogeneous Graphs and Completely Regular Quadrangles

Many known distance-regular graphs have extra combinatorial regularities: One of them is t-homogeneity. A bipartite or almost bipartite distance-regular graph is 2-homogeneous if the number γ _i  = |{x | ∂(u, x) = ∂(v, x) = 1 and ∂(w, x) = i − 1}| (i = 2, 3,..., d) depends only on i whenever ∂(u, v) = 2 and ∂(u, w) = ∂(v, w) = i. K. Nomura gave a complete classification of bipartite and almost bipartite 2-homogeneous distance-regular graphs. In this paper, we generalize Nomura’s results by classifying 2-homogeneous triangle-free distance-regular graphs. As an application, we show that if Γ is a distance-regular graph of diameter at least four such that all quadrangles are completely regular then Γ is isomorphic to a binary Hamming graph, the folded graph of a binary Hamming graph or the coset graph of the extended binary Golay code of valency 24. We also consider the case Γ is a parallelogram-free distance-regular graph. This research was partially supported by the Grant-in-Aid for Scientific Research (No.17540039), Japan Society of the Promotion of Science.     

Distance-Regular Shilla Graphs with <Emphasis Type="Italic">b</Emphasis><Subscript>2</Subscript> = <Emphasis Type="Italic">c</Emphasis><Subscript>2</Subscript>

A Shilla graph is defined as a distance-regular graph of diameter 3 with second eigen-value θ₁ equal to a₃. For a Shilla graph, let us put a = a₃ and b = k/a. It is proved in this paper that a Shilla graph with b₂ = c₂ and noninteger eigenvalues has the following intersection array:

$$\left\{ {\frac{{{b^2}\left( {b - 1} \right)}}{2},\frac{{\left( {b - 1} \right)\left( {{b^2} - b + 2} \right)}}{2},\frac{{b\left( {b - 1} \right)}}{4};1,\frac{{b\left( {b - 1} \right)}}{4},\frac{{b{{\left( {b - 1} \right)}^2}}}{2}} \right\}$$

If Γ is a Q-polynomial Shilla graph with b₂ = c₂ and b = 2r, then the graph Γ has intersection array

$$\left\{ {2tr\left( {2r + 1} \right),\left( {2r + 1} \right)\left( {2rt + t + 1} \right),r\left( {r + t} \right);1,r\left( {r + t} \right),t\left( {4{r^2} - 1} \right)} \right\}$$

and, for any vertex u in Γ, the subgraph Γ₃(u) is an antipodal distance-regular graph with intersection array

$$\left\{ {t\left( {2r + 1} \right),\left( {2r - 1} \right)\left( {t + 1} \right),1;1,t + 1,t\left( {2r + 1} \right)} \right\}$$

The Shilla graphs with b₂ = c₂ and b = 4 are also classified in the paper.

     

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.     

On the Metric Dimension of Imprimitive Distance-Regular Graphs

A resolving set for a graph \({\Gamma}\) is a collection of vertices S, chosen so that for each vertex v, the list of distances from v to the members of S uniquely specifies v. The metric dimension of \({\Gamma}\) is the smallest size of a resolving set for \({\Gamma}\). Much attention has been paid to the metric dimension of distance-regular graphs. Work of Babai from the early 1980s yields general bounds on the metric dimension of primitive distance-regular graphs in terms of their parameters. We show how the metric dimension of an imprimitive distance-regular graph can be related to that of its halved and folded graphs. We also consider infinite families (including Taylor graphs and the incidence graphs of certain symmetric designs) where more precise results are possible.     

The Johnson graph J(d,r) is unique if (d,r) ≠ (2, 8)

We use the classical Root Systems to show the Johnson graph J(d, r) (2 ⩽ 2d ⩽ r < ∞) is the unique distance-regular graph with its intersection numbers when (d, r) ≠ (2, 8). Since this exceptional case has been dealt with by Chang [6] this completes the characterization problem for Johnson graph.