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.     

A Characterization of the Hamming Graphs and the Dual Polar Graphs by Completely Regular Subgraphs

In this paper we study a distance-regular graph Γ of diameter d ≥? 3 which satisfies the following two conditions: (a) For any integer i with 1 ≤? i ≤? d ? 1 and for any pair of vertices at distance i in Γ there exists a strongly closed subgraph of diameter i containing them; (b) There exists a strongly closed subgraph Δ which is completely regular in Γ. It is known that if Δ has diameter 1, then Γ is a regular near polygon. We prove that if a strongly closed subgraph Δ of diameter j with 2 ≤? j ≤? d ? 1 is completely regular of covering radius d ? j in Γ, then Γ is either a Hamming graph or a dual polar 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.     

Parallelogram-free distance-regular graphs having completely regular strongly regular subgraphs

Let Γ=(X,R) be a distance-regular graph of diameter d. A parallelogram of length i is a 4-tuple xyzw consisting of vertices of Γ such that ?(x,y)=?(z,w)=1, ?(x,z)=i, and ?(x,w)=?(y,w)=?(y,z)=i?1. A subset Y of X is said to be a completely regular code if the numbers

$\pi_{i,j}=|\Gamma_{j}(x)\cap Y|\quad (i,j\in \{0,1,\ldots,d\})$

depend only on i=?(x,Y) and j. A subset Y of X is said to be strongly closed if

$\{x\mid \partial(u,x)\leq \partial(u,v),\partial(v,x)=1\}\subset Y,\mbox{ whenever }u,v\in Y.$

Hamming graphs and dual polar graphs have strongly closed completely regular codes. In this paper, we study parallelogram-free distance-regular graphs having strongly closed completely regular codes. Let Γ be a parallelogram-free distance-regular graph of diameter d≥4 such that every strongly closed subgraph of diameter two is completely regular. We show that Γ has a strongly closed subgraph of diameter d?1 isomorphic to a Hamming graph or a dual polar graph. Moreover if the covering radius of the strongly closed subgraph of diameter two is d?2, Γ itself is isomorphic to a Hamming graph or a dual polar graph. We also give an algebraic characterization of the case when the covering radius is d?2.

     

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.     

The spectral excess theorem for distance-regular graphs having distance-<Emphasis Type="Italic">d</Emphasis> graph with fewer distinct eigenvalues

Let \(\Gamma \) be a distance-regular graph with diameter d and Kneser graph \(K=\Gamma _d\), the distance-d graph of \(\Gamma \). We say that \(\Gamma \) is partially antipodal when K has fewer distinct eigenvalues than \(\Gamma \). In particular, this is the case of antipodal distance-regular graphs (K with only two distinct eigenvalues) and the so-called half-antipodal distance-regular graphs (K with only one negative eigenvalue). We provide a characterization of partially antipodal distance-regular graphs (among regular graphs with \(d+1\) distinct eigenvalues) in terms of the spectrum and the mean number of vertices at maximal distance d from every vertex. This can be seen as a more general version of the so-called spectral excess theorem, which allows us to characterize those distance-regular graphs which are half-antipodal, antipodal, bipartite, or with Kneser graph being strongly regular.     

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.     

Collapsible graphs and reductions of line graphs

A graph G is collapsible if for every even subset X⊆V(G), G has a subgraph Γ such that G−E(Γ) is connected and the set of odd-degree vertices of Γ is X. A graph obtained by contracting all the non-trivial collapsible subgraphs of G is called the reduction of G. In this paper, we characterize graphs of diameter two in terms of collapsible subgraphs and investigate the relationship between the line graph of the reduction and the reduction of the line graph. Our results extend former results in [H.-J. Lai, Reduced graph of diameter two, J. Graph Theory 14 (1) (1990) 77-87], and in [P.A. Catlin, Iqblunnisa, T.N. Janakiraman, N. Srinivasan, Hamilton cycles and closed trails in iterated line graphs, J. Graph Theory 14 (1990) 347-364].     

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.     

On the Van Vleck theorem for limit-periodic continued fractions of general form

J. Koolen posed the problem of studying distance-regular graphs in which neighborhoods of vertices are strongly regular graphs with nonprincipal eigenvalue at most t for a given positive integer t. This problem was solved earlier for t = 3. In the case t = 4, the problem was reduced to studying graphs in which neighborhoods of vertices have parameters (352,26,0,2), (352,36,0,4), (243,22,1,2), (729,112,1,20), (204,28,2,4), (232,33,2,5), (676,108,2,20), (85,14,3,2), or (325,54,3,10). In the present paper, we prove that a distance-regular graph in which neighborhoods of vertices are strongly regular with parameters (85, 14, 3, 2) or (325, 54, 3, 10) has intersection array {85, 70, 1; 1, 14, 85} or {325, 270, 1; 1, 54, 325}. In addition, we find possible automorphisms of a graph with intersection array {85, 70, 1; 1, 14, 85}.     

The locally 2-arc transitive graphs admitting an almost simple group of Suzuki type

In this paper, seven families of vertex-intransitive locally (G,2)-arc transitive graphs are constructed, where Sz(q)?G?Aut(Sz(q)), q=²2k+1 for some k∈N. It is then shown that for any graph Γ in one of these families, Sz(q)?Aut(Γ)?Aut(Sz(q)) and that the only locally 2-arc transitive graphs admitting an almost simple group of Suzuki type whose vertices all have valency at least three are (i) graphs in these seven families, (ii) (vertex transitive) 2-arc transitive graphs admitting an almost simple group of Suzuki type, or (iii) double covers of the graphs in (ii). Since the graphs in (ii) have been classified by Fang and Praeger (1999) [6], this completes the classification of locally 2-arc transitive graphs admitting a Suzuki simple group     

Automorphisms of coverings of strongly regular graphs with parameters (81,20,1,6)

The possible orders and subgraphs of fixed points of the automorphisms of distance-regular graphs of diameter 4 which are r-coverings of a strongly regular graph with parameters (81, 20, 1, 6) for r ∈ {2, 3, 6} are found. It is proved that, if the automorphism group of a covering of the above type acts transitively on the set of vertices of the graph, then r = 3.     

On extensions of exceptional strongly regular graphs with eigenvalue 3

The study of distance-regular graphs in which neighborhoods of vertices are strongly regular graphs with eigenvalue 3 was initiated by Makhnev. In particular, he reduced these graphs to graphs in which neighborhoods of vertices are exceptional graphs or pseudogeometric graphs for pG _s?3(s, t). Makhnev and Paduchikh found parameters of exceptional graphs (see the proposition). In the present paper, we study amply regular graphs in which neighborhoods of vertices are exceptional strongly regular graphs with nonprincipal eigenvalue 3 and parameters from conditions 3–6 of the Proposition.     

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 .     

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.     

Distance-regular graphs and (s,c, a,k)-graphs

A diameter-bound theorem for a class of distance-regular graphs which includes all those with even girth is presented. A new class of graphs, called (s, c, a, k)-graphs, is introduced, which are conjectured to contain enough of the local structure of finite distance-regular graphs for them all to be finite. It is proved that they are finite and a bound on the diameter is given in the case a ≤ c.     

Algebraic characterizations of regularity properties in bipartite graphs

Regular and distance-regular characterizations of general graphs are well-known. In particular, the spectral excess theorem states that a connected graph Γ$\Gamma$ is distance-regular if and only if its spectral excess (a number that can be computed from the spectrum) equals the average excess (the mean of the numbers of vertices at extremal distance from every vertex). The aim of this paper is to derive new characterizations of regularity and distance-regularity for the more restricted family of bipartite graphs. In this case, some characterizations of (bi)regular bipartite graphs are given in terms of the mean degrees in every partite set and the Hoffman polynomial. Moreover, it is shown that the conditions for having distance-regularity in such graphs can be relaxed when compared with general graphs. Finally, a new version of the spectral excess theorem for bipartite graphs is presented.     

On the metric dimension of incidence 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$\mu \left(\Gamma \right)$ is the smallest size of a resolving set for $\Gamma$. We consider the metric dimension of two families of incidence graphs: incidence graphs of symmetric designs, and incidence graphs of symmetric transversal designs (i.e. symmetric nets). These graphs are the bipartite distance-regular graphs of diameter 3, and the bipartite, antipodal distance-regular graphs of diameter 4, respectively. In each case, we use the probabilistic method in the manner used by Babai to obtain bounds on the metric dimension of strongly regular graphs, and are able to show that $\mu \left(\Gamma \right)=O(\sqrt{n}logn)$ (where $n$ is the number of vertices).     

Antipodal covering graphs

A graph $\text{Γ}$ of valency k with a group G of automorphisms may be studied via the action of G on the vertex set $\text{V}\text{Γ}$. If G acts transitively on $\text{V}\text{Γ}$, then the notions of primitivity and imprimitivity are meaningful. We consider a natural notion of “block system” for a general graph $\text{Γ}$, which allows us to derive a “quotient” graph Γ whose vertices correspond to the blocks. The ideas are applied to antipodal systems in antipodal graphs: in particular we prove that for an antipodal distance-regular graph, the block size r cannot exceed the valency k; we further show that an antipodal distance-regular graph with r = k is (i) a circuit graph, (ii) a complete bipartite graph, or (iii) a threefold covering of Tutte's trivalent eight-cage.