Search

In this paper we construct distance-regular graphs admitting a vertex transitive action of the five sporadic simple groups discovered by E. Mathieu, the Mathieu groups M 11 , M 12 , M 22 , M 23 and M 24 . From the binary code spanned by an adjacency matrix of the strongly regular graph with parameters (176,70,18,34) we obtain block designs having the full automorphism groups isomorphic to the Higman-Sims finite simple group. Moreover, from that code we obtain eight 2-designs having the full automorphism group isomorphic to M 22 , whose existence cannot be explained neither by the Assmus-Mattson theorem nor by a transitivity argument. Further, we discuss a possibility of permutation decoding of the codes spanned by adjacency matrices of the graphs constructed and find small PD-sets for some of the codes. [ABSTRACT FROM AUTHOR]

A noncomplete graph G $G$ of diameter d $d$ is called an antipodal r $r$‐cover if its vertex set can be partitioned into the subsets (also called fibres) V1,V2,...,Vm ${V}_{1},{V}_{2},\ldots ,{V}_{m}$ of r $r$ vertices each, in such a way that two vertices of G $G$ are at distance d $d$ if and only if they belong to the same fibre. We say that G $G$ is symmetric if for every u∈Vi,v∈Vj $u\in {V}_{i},v\in {V}_{j}$, there exist u′∈Vi $u^{\prime} \in {V}_{i}$ such that d(u,u′)=d(u,v)+d(v,u′) $d(u,u^{\prime})=d(u,v)+d(v,u^{\prime})$, where 1≤i≠j≤m $1\le i\ne j\le m$. In this paper, we prove that, for r≥2 $r\ge 2$, an antipodal r $r$‐cover which is not a cycle, has at least r3d2 $r\unicode{x0230A}\frac{3d}{2}\unicode{x0230B}$ vertices provided d≥3 $d\ge 3$, and at least 2r(d−1) $2r(d-1)$ vertices provided it is symmetric. Our results extend those of Göbel and Veldman. [ABSTRACT FROM AUTHOR]

Let Γ be a diameter 3 distance-regular graph with a strongly regular graph Γ3, where Γ3 is the graph whose vertex set coincides with the vertex set of the graph Γ and two vertices are adjacent whenever they are at distance 3 in the graph Γ. Computing the parameters of Γ3 by the intersection array of the graph Γ is considered as the direct problem. Recovering the intersection array of the graph Γ by the parameters of Γ3 is referred to as the inverse problem. The inverse problem for Γ3 has been solved earlier by A. A. Makhnev and M. S. Nirova. In the case where Γ3 is a pseudo-geometric graph of a net, a series of admissible intersection arrays has been obtained: {c2(u2 − m2) + 2c2m − c2 − 1, c2(u2 − m2), (c2 − 1)(u2 − m2) + 2c2m − c2; 1, c2, u2 − m2} (A. A. Makhnev, Wenbin Guo, M. P. Golubyatnikov). The cases c2 = 1 and c2 = 2 have been examined by A. A. Makhnev, M. P. Golubyatnikov and A. A. Makhnev, M. S. Nirova, respectively. In this paper in the class of graphs with the intersection arrays {mn − 1, (m − 1)(n + 1)}, {n − m + 1}; 1, 1, (m − 1)(n + 1)} all admissible intersection arrays for {3 ≤ m ≤ 13} are found: {20,16,5; 1, 1,16}, {39,36,4; 1, 1,36}, {55,54,2; 1, 2,54}, {90,84,7; 1, 1,84}, {220,216,5; 1, 1,216}, {272,264,9; 1, 1,264} and {350,336,15; 1, 1,336}. It is demonstrated that graphs with the intersection arrays {20,16,5; 1, 1,16}, {39,36,4; 1, 1,36} and {90,84,7; 1, 1,84} do not exist. [ABSTRACT FROM AUTHOR]

A graph is ℓ -reconstructible if it is determined by its multiset of induced subgraphs obtained by deleting ℓ vertices. For graphs with at least six vertices, we prove that all graphs in a family containing all strongly regular graphs and most 2-partially distance-regular graphs are 2-reconstructible. [ABSTRACT FROM AUTHOR]

There exist well-known distance-regular graphs Γ of diameter 3 for which Γ3 is a triangle-free graph. An example is given by the Johnson graph J (8, 3) with the intersection array {15, 8, 3;1, 4, 9}. The paper is concerned with the problem of the existence of distance-regular graphs Γ with the intersection arrays {78, 50, 9;1, 15, 60} and {174, 110, 18;1, 30, 132} for which Γ3 is a triangle-free graph. [ABSTRACT FROM AUTHOR]

A Shilla graph is a distance-regular graph of diameter 3 and second eigenvalue . In case divides put . Furthermore, and has the intersection array . Belousov and Makhnev found the admissible intersection arrays for -polynomial Shilla graphs with which are , where ; ; ; ; ; ; ; and . We prove that there are no graphs with intersection arrays , , or . [ABSTRACT FROM AUTHOR]

The generalized distance matrix of a graph is the matrix whose entries depend only on the pairwise distances between vertices, and the generalized distance spectrum is the set of eigenvalues of this matrix. This framework generalizes many of the commonly studied spectra of graphs. We show that for a large class of graphs these eigenvalues can be computed explicitly. We also present the applications of our results to competition models in ecology and rapidly mixing Markov chains. [ABSTRACT FROM AUTHOR]

In this paper, we introduce the language of a configuration and of t -point counts for distance-regular graphs (DRGs). Every t -point count can be written as a sum of (t − 1) -point counts. This leads to a system of linear equations and inequalities for the t -point counts in terms of the intersection numbers, i.e., a linear constraint satisfaction problem (CSP). This language is a very useful tool for a better understanding of the combinatorial structure of distance-regular graphs. Among others we prove a new diameter bound for DRGs that is tight for the Biggs–Smith graph. We also obtain various old and new inequalities for the parameters of DRGs, including the diameter bounds by Terwilliger. [ABSTRACT FROM AUTHOR]

Let Γ be a distance-regular graph of diameter d with classical parameters (d , b , α , β) with b < − 1. Van Dam, Koolen and Tanaka [Distance-regular graphs, Electron. J. Combin. (2016) DS22] surveyed the classification of Γ. From this survey, the following four cases have not been studied: (1) d ≥ 3 , c 2 = a 1 = 1 ; (2) d ≥ 3 , c 2 = 1 , a 2 = a 1 > 1 ; (3) d = 3 , c 2 = 1 , a 2 > a 1 > 1 ; (4) d = 3 , c 2 > 1 , a 1 ≥ 1. Here a i , b i , c i (0 ≤ i ≤ d) are the intersection numbers of Γ. In this paper, we study the above four cases. Our main results are as follows. For the case (1), Γ is the triality graph ▪; for the case (2), Γ is the collinearity graph of a generalized hexagon of order (a 1 + 1 , (a 1 + 1) 3). In particular, if a 1 + 1 is a prime power, then the classical parameters of Γ are realized by the triality graphs ▪; for the case (3), Γ does not exist; for the case (4), precisely one of the following (i)–(iv) holds: (i) Γ is the dual polar graph ▪, where a 1 + 1 is a prime power; (ii) Γ is the extended ternary Golay code graph; (iii) Γ is the large Witt graph M 24 ; (iv) Γ is the collinearity graph of a maximal regular near hexagon with classical parameters (d , b , α , β) = (3 , − a 1 − 1 , − c 2 + a 1 a 1 , (a 1 + 1) (c 2 + a 1 + 1)) with a 1 ≥ 2 , 2 ≤ c 2 ≤ (a 1) 2 + a 1 + 1. In particular, if 2 ≤ a 1 ≤ 10 7 − 1 , then c 2 = 2 and a 1 ∈ { 3 , 4 , 7 , 10 , 17 , 22 , 31 , 52 , 157 }. [ABSTRACT FROM AUTHOR]

A quasi-strongly regular graph G of grade 2 with parameters (n , k , a ; c 1 , c 2) is a k -regular graph on n vertices such that every pair of adjacent vertices have a common neighbors, every pair of distinct nonadjacent vertices have c 1 or c 2 common neighbors, and for each c i (i = 1 , 2) , there exists a pair of non-adjacent vertices sharing c i common neighbors. The children G 1 and G 2 of the graph G are defined on the vertex set of G such that every two distinct vertices are adjacent in G 1 or G 2 if and only if they share c 1 or c 2 neighbors, respectively. The graph G is a quasi-strongly regular graph of type A or B if it is of grade 2 and has a child that is a connected strongly regular graph or a disjoint union of cliques of order m (m > 1) , respectively. In this paper, we investigate the spectral properties of the graph G if it is a quasi-strongly regular graph of type A or B. Several examples of distance-regular graphs which are quasi-strongly regular graphs of type A are given. Moreover, we give several constructions of quasi-strongly regular graphs and calculate their spectrum. [ABSTRACT FROM AUTHOR]

Let Γ be a distance-regular graph of diameter 3 with c2 = 2 (any two vertices with distance 2 between them have exactly two common neighbors). Then the neighborhood Δ of the vertex w in Γ is a partial line space. In view of the Brouwer–Neumaier result either Δ is the union of isolated (λ + 1)-cliques or the degrees of vertices k ≥ λ(λ + 3)/2, and in the case of equality k = 5, λ = 2 and Γ is the icosahedron graph. A. A. Makhnev, M. P. Golubyatnikov and Wenbin Guo have investigated distance-regular graphs Γ of diameter 3 such that Γ 3 is the pseudo-geometrical network graph. They have found a new infinite set {2u2 −2m2 + 4m − 3,2u2 −2m2,u2 − m2 + 4m −2;1, 2, u2 − m2} of feasible intersection arrays for such graphs with c2 = 2. Here we prove that some distance-regular graphs from this set do not exist. It is proved also that distance-regular graph with intersection array {22, 16, 5; 1, 2, 20} does not exist. [ABSTRACT FROM AUTHOR]

• In this paper, we characterize Hamming and Johnson graphs by their spectral gap. • We confirm Babai's conjecture on the motion of distance-regular graphs of bounded diameter. • Our characterization of Hamming graphs involves only inequality constraints. One of the central results in the representation theory of distance-regular graphs classifies distance-regular graphs with μ ≥ 2 and second largest eigenvalue θ 1 = b 1 − 1. In this paper we give a classification under the (weaker) approximate eigenvalue constraint θ 1 ≥ (1 − ε) b 1 for the class of geometric distance-regular graphs. As an application, we confirm Babai's conjecture on the minimal degree of the automorphism group of distance-regular graphs of bounded diameter. This conjecture asserts that if X is a primitive distance-regular graph with n vertices, and X is not a Hamming graph or a Johnson graph, then the automorphism group Aut (X) has minimal degree ≥ c n for some constant c > 0. It follows that Aut (X) satisfies strong structural constraints. [ABSTRACT FROM AUTHOR]

We prove that a distance-regular graph with a dominant distance is a spectral expander. The key ingredient of the proof is a new inequality on the intersection numbers. We use the spectral gap bound to study the structure of the automorphism group. The minimal degree of a permutation group G is the minimum number of points not fixed by non-identity elements of G. Lower bounds on the minimal degree have strong structural consequences on G. In 2014 Babai proved that the automorphism group of a strongly regular graph with n vertices has minimal degree ≥ c n , with known exceptions. Strongly regular graphs correspond to distance-regular graphs of diameter 2. Babai conjectured that Hamming and Johnson graphs are the only primitive distance-regular graphs of diameter d ≥ 3 whose automorphism group has sublinear minimal degree. We confirm this conjecture for non-geometric primitive distance-regular graphs of bounded diameter. We also show if the primitivity assumption is removed, then only one additional family of exceptions arises, the crown graphs. We settle the geometric case in a companion paper. [ABSTRACT FROM AUTHOR]

We give a survey on graphs with fixed smallest adjacency eigenvalue, especially on graphs with large minimal valency and also on graphs with good structures. Our survey mainly consists of the following two parts: Hoffman graphs, the basic theory related to Hoffman graphs and the applications of Hoffman graphs to graphs with fixed smallest adjacency eigenvalue and large minimal valency; recent results on distance-regular graphs and co-edge regular graphs with fixed smallest adjacency eigenvalue and the characterizations of certain families of distance-regular graphs. At the end of the survey, we also discuss signed graphs with fixed smallest adjacency eigenvalue and present some new findings. [ABSTRACT FROM AUTHOR]

We introduce a pictorial notation for certain tensors arising in the study of association schemes, based on earlier ideas of Terwilliger, Neumaier and Jaeger. These tensors, which we call "scaffolds", obey a simple set of rules which generalize common linear-algebraic operations such as trace, matrix product and entrywise product. We first study an elementary set of "moves" on scaffolds and illustrate their use in combinatorics. Next we re-visit results of Dickie, Suzuki and Terwilliger. The main new results deal with the relationships among vector spaces of scaffolds with edge weights chosen from a fixed coherent algebra and various underlying diagrams. As one consequence, we provide simple descriptions of the Terwilliger algebras of triply regular and dually triply regular association schemes. We finish with a conjecture connecting the duality of Bose-Mesner algebras to the graph-theoretic duality of circular planar graphs. [ABSTRACT FROM AUTHOR]

A distance-regular graph of diameter 3 with the second eigenvalue is called a Shilla graph. For a Shilla graph Γ, the number a = a3 divides k and we set . Three infinite families of Shilla graphs with the following admissible intersection arrays were found earlier: {b(b2 – 1), b2(b – 1), b2; 1, 1, (I.N. Belousov), , (Koolen, Park), and {(s + 1) (Belousov). In this paper, it is proved that, in the first family, there exists a unique graph, namely, a generalized hexagon of order 2, whereas there are no graphs in the second or third families. [ABSTRACT FROM AUTHOR]

Let V denote a vector space with finite positive dimension. We consider an ordered pair of linear transformations A : V → V and A ∗ : V → V that satisfy (i) and (ii) below. There exists a basis for V with respect to which the matrix representing A is irreducible tridiagonal and the matrix representing A ∗ is diagonal. There exists a basis for V with respect to which the matrix representing A ∗ is irreducible tridiagonal and the matrix representing A is diagonal. We call such a pair a Leonard pair on V. In the literature, there are some parameters that are used to describe Leonard pairs called the intersection numbers { a i } i = 0 d , { b i } i = 0 d − 1 , { c i } i = 1 d , and the dual eigenvalues { θ i ∗ } i = 0 d . In this paper, we provide two characterizations of Leonard pairs. For the first characterization, the focus is on the { a i } i = 0 d and { θ i ∗ } i = 0 d . For the second characterization, the focus is on the { b i } i = 0 d − 1 , { c i } i = 1 d , and { θ i ∗ } i = 0 d . [ABSTRACT FROM AUTHOR]

In this research paper we begin with study of family of n dimensional hyper cube graphs and establish some properties related to their distance, spectra, and multiplicities and associated eigen vectors and extend to bipartite double graphs[11]. In a more involved way since no complete characterization was available with experiential results in several inter connection networks on this spectra our work will add an element to existing theory. [ABSTRACT FROM AUTHOR]

We point out possible automorphisms of a distance-regular graph Γ with intersection array {55, 54, 2; 1, 1, 54} and spectrum 551, 71617,−1110,−81408. [ABSTRACT FROM AUTHOR]

We study regular graphs whose distance-2 graph or distance-1-or-2 graph is strongly regular. We provide a characterization of such graphs Γ (among regular graphs with few distinct eigenvalues) in terms of the spectrum and the mean number of vertices at maximal distance d from every vertex, where d+1 is the number of different eigenvalues of Γ. This can be seen as another version of the so-called spectral excess theorem, which characterizes in a similar way those regular graphs that are distance-regular. [ABSTRACT FROM AUTHOR]

Characterization of some classes of graphs inducing periodic Grover walks have been studied for recent years. In particular, for the strongly regular graphs, it has been known that there are only three kinds of such graphs. As an extension of this result, we focus on the periodicity of the Grover walks on distance-regular graphs. The distance-regular graph is regarded as a kind of generalization of the strongly regular graph. In this paper, we find some classes of distance-regular graphs admitting a periodic Grover walk and obtain a useful necessary condition to induce periodic Grover walks. Also, we apply this necessary condition to give another proof for the classification of the strongly regular graphs. [ABSTRACT FROM AUTHOR]

In this paper we show that for a given integer m ≥ 3 , there are only finitely many antipodal distance-regular graphs with c 2 ≥ 2 , odd diameter at least 5 and smallest eigenvalue at least - m . To prove this we first show that for a given integer m ≥ 3 , there are only finitely many antipodal distance-regular graphs with c 2 ≥ 2 , diameter at least 5 and smallest eigenvalue at least - m such that folded graphs are non-geometric. (A non-complete distance-regular graph is called geometric if it is the point graph of a partial linear space in which the set of lines is a set of Delsarte cliques.). Moreover, we show tight bounds for the diameter of geometric antipodal distance-regular graphs with an induced subgraph K 2 , 1 , 1 by studying parameters for geometric antipodal distance-regular graphs. [ABSTRACT FROM AUTHOR]

Cameron-Liebler sets were originally defined as collections of lines ("line classes") in PG (3 , q) sharing certain properties with line classes of symmetric tactical decompositions. While there are many equivalent characterisations, these objects are defined as sets of lines whose characteristic vector lies in the image of the transpose of the point-line incidence matrix of PG (3 , q) , and so combinatorially they behave like a union of pairwise disjoint point-pencils. Recently, the concept of a Cameron-Liebler set has been generalised to several other settings. In this article we introduce Cameron-Liebler sets of generators in finite classical polar spaces. For each of the polar spaces we give a list of characterisations that mirrors those for Cameron-Liebler line sets, and also prove some classification results. [ABSTRACT FROM AUTHOR]

Abstract This is a survey on some known properties of the possible Moore graph (or graphs) ϒ with degree 57 and diameter 2. Moreover, we give some new results about it, such as the following. When we consider the distance partition of ϒ induced by a vertex subset C , the following graphs are distance-regular: The induced graph of the vertices at distance 1 from C when C is a set of 400 independent vertices; the induced graphs of the vertices at distance 2 from C when C is a vertex or an edge, and the line graph of ϒ. Besides, ϒ is an edge-distance-regular graph. [ABSTRACT FROM AUTHOR]

It is proved that the automorphism group of every AT4(5, 7, r)-graph acts intransitively on the set of its arcs. Moreover, it is established that the automorphism group of any strongly regular graph with parameters (329, 40, 3, 5) acts intransitively on the set of its vertices. [ABSTRACT FROM AUTHOR]

Abstract We prove a conjecture by Van Dam & Sotirov on the smallest eigenvalue of (distance- j) Hamming graphs and a conjecture by Karloff on the smallest eigenvalue of (distance- j) Johnson graphs. More generally, we study the smallest eigenvalue and the second largest eigenvalue in absolute value of the graphs of the relations of classical P - and Q -polynomial association schemes. [ABSTRACT FROM AUTHOR]

We prove the existence of strongly regular graphs with parameters (216, 40, 4, 8) and (540, 187, 58, 68). We also construct a strongly regular graph with parameters (540, 224, 88, 96) that was previously unknown. Further, we construct all distance-regular graphs with at most 600 vertices, admitting a transitive action of the orthogonal group O + ( 6 , 2 ) or O − ( 6 , 2 ) . Furthermore, we show that under certain conditions an orbit matrix M of a strongly regular graph Γ can be used to define a new strongly regular graph Γ ˜ , where the vertices of the graph Γ ˜ correspond to the orbits of Γ (the rows of M ). We show that some of the obtained strongly regular graphs are related to each other in a way that one can be constructed from an orbit matrix of the other. [ABSTRACT FROM AUTHOR]

We consider a primitive distance-regular graph Γ with diameter at least 3. We use the intersection numbers of Γ to find a positive semidefinite matrix G with integer entries. We show that G has determinant zero if and only if Γ is Q-polynomial. [ABSTRACT FROM AUTHOR]

Let Γ denote the Hamming graph H(D, r) with r≥3. Consider the distance matrices {Ai}i=0D of Γ. Fix a vertex x of Γ, and consider the dual distance matrices {Ai∗}i=0D of Γ with respect to x. We investigate the group commutator AD-1AD∗-1ADAD∗. We show that this matrix is diagonalizable. We compute its eigenvalues and their eigenspaces. Let T denote the subconstituent algebra of Γ with respect to x. We describe the action of AD-1AD∗-1ADAD∗ on each irreducible T-module. [ABSTRACT FROM AUTHOR]

The positive part U q + of U q ( sl ˆ 2) has a presentation with two generators W 0 , W 1 and two relations called the q -Serre relations. The algebra U q + contains some elements, said to be alternating. There are four kinds of alternating elements, denoted { W − k } k ∈ N , { W k + 1 } k ∈ N , { G k + 1 } k ∈ N , { G ˜ k + 1 } k ∈ N. The alternating elements of each kind mutually commute. A tridiagonal pair is an ordered pair of diagonalizable linear maps A , A ⁎ on a nonzero, finite-dimensional vector space V , that each act in a (block) tridiagonal fashion on the eigenspaces of the other one. Let A , A ⁎ denote a tridiagonal pair on V. Associated with this pair are six well-known direct sum decompositions of V ; these are the eigenspace decompositions of A and A ⁎ , along with four decompositions of V that are often called split. In our main results, we assume that A , A ⁎ has q -Serre type. Under this assumption A , A ⁎ satisfy the q -Serre relations, and V becomes an irreducible U q + -module on which W 0 = A and W 1 = A ⁎. We describe how the alternating elements of U q + act on the above six decompositions of V. We show that for each decomposition, every alternating element acts in either a (block) diagonal, (block) upper bidiagonal, (block) lower bidiagonal, or (block) tridiagonal fashion. We investigate two special cases in detail. In the first case the eigenspaces of A and A ⁎ all have dimension one. In the second case A and A ⁎ are obtained by adjusting the adjacency matrix and a dual adjacency matrix of a distance-regular graph that has classical parameters and is formally self-dual. [ABSTRACT FROM AUTHOR]

An antipodal nonbipartite distance-regular graph Γ of diameter 3 has an intersection array () and eigenvalues k, n, –1, and –m, where n and –m are the roots of the quadratic equation . The Krein bound gives if . In the case , following Godsil, we call Γ an antipodal Krein graph. The point graph Σ of having spread gives an antipodal Krein graph with . If Σ has an automorphism σ of order f that fixes every component of the spread, then the graph whose vertices are σ-orbits on a point set and two orbits are adjacent if a vertex of one orbit is adjacent to a vertex of the other is a distance-regular graph with intersection array {q3, and every local subgraph Δ(u) is pseudogeometric for . If f = 2, then we have a pseudogeometric graph for . Hence, a locally pseudo GQ(4, 6) graph with intersection array {125, 96, 1; 1, 48, 125} and a locally pseudo GQ(6, 8) graph with intersection array {343, 288, 1; 1, 96, 343} exist. [ABSTRACT FROM AUTHOR]

We complete the classification of edge-symmetric distance-regular coverings of complete graphs with r /∉ {2, k, (k − 1)/μ} for the case of the almost simple action of an automorphism group of a graph on a set of its antipodal classes; here r is the order of an antipodal class. [ABSTRACT FROM AUTHOR]

A resolving set for a graph Γ 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 μ ( Γ ) is the smallest size of a resolving set for Γ . 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 μ ( Γ ) = O ( n log n ) (where n is the number of vertices). [ABSTRACT FROM AUTHOR]

An association scheme is called partially metric if it has a connected relation whose distance-two relation is also a relation of the scheme. In this paper we determine the symmetric partially metric association schemes with a multiplicity three. Besides the association schemes related to regular complete 4-partite graphs, we obtain the association schemes related to the Platonic solids, the bipartite double scheme of the dodecahedron, and three association schemes that are related to well-known 2-arc-transitive covers of the cube: the Möbius–Kantor graph, the Nauru graph, and the Foster graph F048A. In order to obtain this result, we also determine the symmetric association schemes with a multiplicity three and a connected relation with valency three. Moreover, we construct an infinite family of cubic arc-transitive 2-walk-regular graphs with an eigenvalue with multiplicity three that give rise to non-commutative association schemes with a symmetric relation of valency three and an eigenvalue with multiplicity three. [ABSTRACT FROM AUTHOR]

A Shilla graph is defined as a distance-regular graph of diameter 3 with second eigen-value θ1 equal to a3. For a Shilla graph, let us put a = a3 and b = k/a. It is proved in this paper that a Shilla graph with b2 = c2 and noninteger eigenvalues has the following intersection array: {b2(b−1)2,(b−1)(b2−b+2)2,b(b−1)4;1,b(b−1)4,b(b−1)22} If Γ is a Q-polynomial Shilla graph with b2 = c2 and b = 2r, then the graph Γ has intersection array {2tr(2r+1),(2r+1)(2rt+t+1),r(r+t);1,r(r+t),t(4r2−1)} and, for any vertex u in Γ, the subgraph Γ3(u) is an antipodal distance-regular graph with intersection array {t(2r+1),(2r−1)(t+1),1;1,t+1,t(2r+1)} The Shilla graphs with b2 = c2 and b = 4 are also classified in the paper. [ABSTRACT FROM AUTHOR]

Recently it was shown that a distance-regular graph in which neighbourhoods of vertices are strongly regular with parameters (99,14,1,2) has intersection array {99, 84, 1; 1, 14, 99}, {99, 84, 1; 1, 12, 99} or {99, 84, 30; 1, 6, 54}. In the present paper we find possible automorphisms of a graph with the intersection array {99, 84, 30; 1, 6, 54}. It is shown, in particular, that such a graph is not point-symmetric. [ABSTRACT FROM AUTHOR]

We investigate { 0 , 1 , … , t } -cliques of generators on dual polar graphs of finite classical polar spaces of rank d . These cliques are also known as Erdős–Ko–Rado sets in polar spaces of generators with pairwise intersections in at most codimension t . Our main result is that we classify all such cliques of maximum size for t ≤ 8 d / 5 − 2 if q ≥ 3 , and t ≤ 8 d / 9 − 2 if q = 2 . We have the following byproducts. (a) For q ≥ 3 we provide estimates of Hoffman's bound on these { 0 , 1 , … , t } -cliques for all t . (b) For q ≥ 3 we determine the largest, second largest, and smallest eigenvalue of the graphs which have the generators of a polar space as vertices and where two generators are adjacent if and only if they meet in codimension at least t + 1 . Furthermore, we provide nice explicit formulas for all eigenvalues of these graphs. (c) We provide upper bounds on the size of the second largest maximal { 0 , 1 , … , t } -cliques for some t . [ABSTRACT FROM AUTHOR]

Let Γ be a distance regular graph with intersection array {35, 32, 1; 1, 4, 35} and let G = Aut(Γ) act transitively on the set of vertices of the graph Γ. It is shown that G is a {2, 3}-group. [ABSTRACT FROM AUTHOR]

In this paper we characterize distance-regular graphs with diameter three having exactly three distinct distance eigenvalues, and also bipartite distance-regular graphs with diameter four having three distinct distance eigenvalues. We derive some properties and give particular examples of such graphs. We also present an infinite family of bipartite semiregular graphs with diameter four having exactly four distinct distance eigenvalues. With these results, we address some problems posed in Atik and Panigrahi (2015) [3] . [ABSTRACT FROM AUTHOR]

For a distance-regular graph of diameter three Γ, the statement that distance-3 graph Γ 3 of Γ is strongly regular is equivalent to that Γ has eigenvalue −1. There are many distance-regular graphs of diameter 3 having eigenvalue −1, such as the folded 7-cube, generalized hexagons of order ( s , s ) and antipodal nonbipartite distance-regular graphs of diameter 3. In this paper, we show that for a fixed positive integer α ( β , respectively), there are only finitely many distance-regular graphs of diameter 3 having eigenvalue −1 and a 3 = α ( b 1 c 2 = β and a 3 ≠ 0 , respectively). Such distance-regular graphs for small numbers α = 1 , 2 or β = 3 with a 3 ≠ 0 are classified. We show that there are no distance-regular graphs with intersection array { 44 , 35 , 3 ; 1 , 5 , 42 } . Moreover, we classify the distance-regular graphs with diameter 3 and smallest eigenvalue greater than −3. [ABSTRACT FROM AUTHOR]

We consider undirected graphs without loops and multiple edges. Previously, V. P. Burichenko and A. A. Makhnev [1] found intersection arrays of distance-regular locally cyclic graphs with the number of vertices at most 1000. It is shown that the automorphism group of a graph with intersection array {15, 12, 1; 1, 2, 15}, {35, 32, 1; 1, 2, 35}, {39, 36, 1; 1, 2, 39}, or {42, 39, 1; 1, 3, 42} (such a graph enters the above-mentioned list) acts intransitively on the set of its vertices. [ABSTRACT FROM AUTHOR]

We define the type of graph products, which enable us to treat many graph products in a unified manner. These unified graph products are shown to be compatible with Godsil-McKay switching. Furthermore, by this compatibility, we show that the Doob graphs can also be obtained from the Hamming graphs by switching. [ABSTRACT FROM AUTHOR]

We construct several classes of completely regular codes with different parameters, but identical intersection array. Given a prime power q and any two natural numbers a , b , we construct completely transitive codes over different fields with covering radius ρ = min { a , b } and identical intersection array, specifically, one code over F q r for each divisor r of a or b . As a corollary, for any prime power q , we show that distance regular bilinear forms graphs can be obtained as coset graphs from several completely regular codes with different parameters. [ABSTRACT FROM AUTHOR]

In his famous theorem (1982), Douglas Leonard characterized the q -Racah polynomials and their relatives in the Askey scheme from the duality property of Q -polynomial distance-regular graphs. In this paper we consider a nonsymmetric (or Laurent) version of the q -Racah polynomials in the above situation. Let Γ denote a Q -polynomial distance-regular graph that contains a Delsarte clique C . Assume that Γ has q -Racah type. Fix a vertex x ∈ C . We partition the vertex set of Γ according to the path-length distance to both x and C . The linear span of the characteristic vectors corresponding to the cells in this partition has an irreducible module structure for the universal double affine Hecke algebra H ˆ q of type ( C 1 ∨ , C 1 ) . From this module, we naturally obtain a finite sequence of orthogonal Laurent polynomials. We prove the orthogonality relations for these polynomials, using the H ˆ q -module and the theory of Leonard systems. Changing H ˆ q by H ˆ q − 1 we show how our Laurent polynomials are related to the nonsymmetric Askey–Wilson polynomials, and therefore how our Laurent polynomials can be viewed as nonsymmetric q -Racah polynomials. [ABSTRACT FROM AUTHOR]

In this paper, we classify antipodal distance-regular graphs of diameter three that admit an arc-transitive action of S U 3 ( q ) . In particular, we find a new infinite family of distance-regular antipodal r -covers of a complete graph on q 3 + 1 vertices, where q is odd and r is any divisor of q + 1 such that ( q + 1 ) ∕ r is odd. Further, we find several new constructions of arc-transitive antipodal distance-regular graphs of diameter three in case λ = μ . [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

In this paper we consider the concept of preintersection numbers of a graph. These numbers are determined by the spectrum of the adjacency matrix of the graph, and generalize the intersection numbers of a distance-regular graph. By using the preintersection numbers we give some new spectral and quasi-spectral characterizations of distance-regularity, in particular for graphs with large girth or large odd-girth. [ABSTRACT FROM AUTHOR]

In this paper, we study the incidence algebra T of the attenuated space poset A q ( N , M ) . We consider the following topics. We consider some generators of T : the raising matrix R , the lowering matrix L , and a certain diagonal matrix K . We describe some relations among R , L , K . We put these relations in an attractive form using a certain matrix S in T . We characterize the center Z ( T ) . Using Z ( T ) , we relate T to the quantum group U τ ( sl 2 ) with τ 2 = q . We consider two elements A , A ⁎ in T of a certain form. We find necessary and sufficient conditions for A , A ⁎ to satisfy the tridiagonal relations. Let W denote an irreducible T -module. We find necessary and sufficient conditions for the above A , A ⁎ to act on W as a Leonard pair. [ABSTRACT FROM AUTHOR]