TOPICS
Search

Shrikhande Graph


ShrikhandeGraph

The Shrikhande graph is a strongly regular graph on 16 nodes. It is cospectral with the rook graph L_(4,4), so neither of the two is determined by spectrum.

The Shrikhande graph is the smallest distance-regular graph that is not distance-transitive (Brouwer et al. 1989, p. 136). It has intersection array {6,3;1,2}.

The Shrikhande graph is implemented in the Wolfram Language as GraphData["ShrikhandeGraph"].

ShrikhandeLCF

The Shrikhande graph has two generalized LCF notations of order 8, eleven of order 4, 53 of order 2, and 2900 of order 1. The graphs with LCF notations of orders four and eight are illustrated above.

The Shrikhande graph appears on the cover of the book Combinatorial Matrix Theory by Brualdi and Ryser (1991); illustrated above.

ShrikhandeGraphMatrices

The plots above show the adjacency, incidence, and graph distance matrices for the Shrikhande graph.

It is an integral graph with graph spectrum (-2)^92^66^1.

The bipartite double graph of the Shrikhande graph is the Kummer graph.

The following table summarizes some properties of the Shrikhande graph.

propertyvalue
automorphism group order192
characteristic polynomial(x-6)(x-2)^6(x+2)^9
chromatic number4
chromatic polynomial?
claw-freeno
clique number3
graph complement name?
determined by spectrumno
diameter2
distance-regular graphyes
dual graph nameDyck graph
edge chromatic number6
edge connectivity6
edge count48
edge transitiveyes
Eulerianyes
girth3
Hamiltonianyes
Hamiltonian cycle count562464
Hamiltonian path count?
integral graphyes
independence number4
line graphno
line graph name?
perfect matching graphno
planarno
polyhedral graphno
radius2
regularyes
square-freeno
strongly regular parameters(16,6,2,2)
symmetricyes
traceableyes
triangle-freeno
vertex connectivity6
vertex count16
vertex transitiveyes

See also

Cospectral Graphs, Determined by Spectrum, Doob Graph, Integral Graph, Strongly Regular Graph, Triangular Graph

Explore with Wolfram|Alpha

References

Brouwer, A. E. "Shrikhande Graph." http://www.win.tue.nl/~aeb/drg/graphs/Shrikhande.html.Brouwer, A. E.; Cohen, A. M.; and Neumaier, A. Distance-Regular Graphs. New York: Springer-Verlag, pp. 104-105 and 136, 1989.Brouwer, A. E. and van Lint, J. H. "Strongly Regular Graphs and Partial Geometries." In Enumeration and Design: Papers from the conference on combinatorics held at the University of Waterloo, Waterloo, Ont., June 14-July 2, 1982 (Ed. D. M. Jackson and S. A. Vanstone). Toronto, Canada: Academic Press, pp. 85-122, 1984.Brualdi, R. and Ryser, H. J. Combinatorial Matrix Theory. New York: Cambridge University Press, p. 153, 1991.DistanceRegular.org. "Shrikhande Graph." http://www.distanceregular.org/graphs/shrikhande.html.Shrikhande, S.-C. S. "The Uniqueness of the L_2 Association Scheme." Ann. Math. Stat. 30, 781-798, 1959.van Dam, E. R. and Haemers, W. H. "Which Graphs Are Determined by Their Spectrum?" Lin. Algebra Appl. 373, 139-162, 2003.

Cite this as:

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

Subject classifications