TOPICS
Search

Geometric Graph


A connected distance-regular graph Gamma on two or more vertices that contains a set of Delsarte cliques C such that every edge of Gamma lies in a unique member of C is known as a geometric distance-regular graph (Koolen et al. 2023). The concept of geometric graphs was first defined by Bose (1963) for strongly regular graphs and subsequently extended to distance-regular graphs by Godsil (1993).

Koolen et al. (2023) enumerate 18 cases of non-geometric distance-regular graphs of graph diameter at least 3 with smallest graph eigenvalue at least -3, where the distance-regular graph with intersection array {18,12,1;1,2,18} is putative and the odd n-cycles with n>3 (which satisfy all the given criteria) are apparently silently omitted.

Classes of graphs that are geometric include the Johnson graphs and Hamming graphs (Koolen et al. 2023), which in turn include complete graphs, hypercube graphs, n×n rook graphs, triangular graphs, and tetrahedral Johnson graphs.


See also

Delsarte Bound, Delsarte Clique

Explore with Wolfram|Alpha

References

Bose, R. "STrongly Regular Graphs, Partial Geometries and Partially Balanced Designs." Pacific J. Math. 13, 389-419, 1963.Godsil, C. "Geometric Distance-Regular Covers." New Zealand J. Math. 22, 31-38, 1993.Koolen, J. H.; Yu, K.; Liang, X.; Choi, H.; and Markowsky, G. "Non-Geometric Distance-Regular Graphs of Diameter at Least 3 With Smallest Eigenvalue at Least -3." 15 Nov 2023. https://arxiv.org/abs/2311.09001.

Cite this as:

Weisstein, Eric W. "Geometric Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/GeometricGraph.html

Subject classifications