Search

We prove that any completely regular code with minimum eigenvalue in any geometric graph Γ corresponds to a completely regular code in the clique graph of Γ. Studying the interrelation of these codes, a complete characterization of the completely regular codes in the Johnson graphs J (n , w) with covering radius w − 1 and strength 1 is obtained. In particular this result finishes a characterization of the completely regular codes in the Johnson graphs J (n , 3). We also classify the completely regular codes of strength 1 in the Johnson graphs J (n , 4) with only one case for the eigenvalues left open. [ABSTRACT FROM AUTHOR]

We give a new bound on the parameter $$\lambda $$ (number of common neighbors of a pair of adjacent vertices) in a distance-regular graph G, improving and generalizing bounds for strongly regular graphs by Spielman (1996) and Pyber (2014. ). The new bound is one of the ingredients of recent progress on the complexity of testing isomorphism of strongly regular graphs (Babai et al. 2013). The proof is based on a clique geometry found by Metsch (Des Codes Cryptogr 1(2):99-116, 1991) under certain constraints on the parameters. We also give a simplified proof of the following asymptotic consequence of Metsch's result: If $$k\mu = o(\lambda ^2)$$ , then each edge of G belongs to a unique maximal clique of size asymptotically equal to $$\lambda $$ , and all other cliques have size $$o(\lambda )$$ . Here k denotes the degree and $$\mu $$ the number of common neighbors of a pair of vertices at distance 2. We point out that Metsch's cliques are 'asymptotically Delsarte' when $$k\mu = o(\lambda ^2)$$ , so families of distance-regular graphs with parameters satisfying $$k\mu = o(\lambda ^2)$$ are 'asymptotically Delsarte-geometric.' [ABSTRACT FROM AUTHOR]

A spread of strongly regular graphs is a partition of the vertex set by Delsarte cliques. We consider imprimitive association schemes of class four which are two-fold covers of strongly regular graphs with spreads. It will be shown that a two-fold cover of a strongly regular graph with a spread provides a five class fission scheme of the imprimitive scheme of class four. [ABSTRACT FROM AUTHOR]

Abstract: A non-complete distance-regular graph Γ is called geometric if there exists a set of Delsarte cliques such that each edge of lies in a unique clique in . In this paper we determine the non-complete distance-regular graphs satisfying . To prove this result, we first show by considering non-existence of 4-claws that any non-complete distance-regular graph satisfying is a geometric distance-regular graphs smallest eigenvalue −3. Moreover, we classify the geometric distance-regular graphs with smallest eigenvalue −3. As an application, two feasible intersection arrays in the list of [7, Chapter 14] are ruled out. [Copyright &y& Elsevier]

Let Γ be a Delsarte set graph with an intersection number c2 (i.e., a distance-regular graph with a set C of Delsarte cliques such that each edge lies in a positive constant number nC of Delsarte cliques in C). We showed in Bang et al. (J Combin 28:501-506, 2007) that if ψ1 > 1 then c2 ≥ 2ψ1 where ψ1 := ΙΓ1 (x)∩CΙ for x ∈ V(Γ) and C a Delsarte clique satisfying d(x,C) = 1. In this paper,we classify Γ with the case c2 = 2ψ1 > 2. As a consequence of this result, we show that if c2 ≤ 5 and ψ1 > 1 then Γ is either a Johnson graph or a folded Johnson graph J (4s, 2s) with s ≥ 3. [ABSTRACT FROM AUTHOR]

Let Γ be a Delsarte set graph with an intersection number c2 (i.e., a distance-regular graph with a set C of Delsarte cliques such that each edge lies in a positive constant number nC of Delsarte cliques in C). We showed in Bang et al. (J Combin 28:501-506, 2007) that if ψ1 > 1 then c2 ≥ 2ψ1 where ψ1 := ΙΓ1 (x)∩CΙ for x ∈ V(Γ) and C a Delsarte clique satisfying d(x,C) = 1. In this paper,we classify Γ with the case c2 = 2ψ1 > 2. As a consequence of this result, we show that if c2 ≤ 5 and ψ1 > 1 then Γ is either a Johnson graph or a folded Johnson graph J (4s, 2s) with s ≥ 3. [ABSTRACT FROM AUTHOR]