Article ID Journal Published Year Pages File Type
8903168 Discrete Mathematics 2018 8 Pages PDF
Abstract
A non-complete distance-regular graph is called geometric if there exists a set C of Delsarte cliques such that each edge lies in exactly one clique in C. Let Γ be a geometric distance-regular graph with diameter D≥3 and smallest eigenvalue θD. In this paper we show that if Γ contains an induced subgraph K2,1,1, then D≤−θD. Moreover, if −θD−1≤D≤−θD then D=−θD and Γ is a Johnson graph. We also show that for (s,b)⁄∈{(11,11),(21,21)}, there are no distance-regular graphs with intersection array {4s,3(s−1),s+1−b;1,6,4b} where s,b are integers satisfying s≥3 and 2≤b≤s. As an application of these results, we classify geometric distance-regular graphs with D≥3, θD≥−4 and containing an induced subgraph K2,1,1.
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
,