Count Shrikhande

Count Shrikhande
Count Shrikhande
Named after	S. S. Shrikhande
Top	sixteen
Riber	48
Radius	2
Diameter	2
Girth	3
Automorphisms	192
Chromatic number	four
Chromatic Index	6
The properties	Very regular; Hamilton; Symmetric; Euler; Whole
Book thickness	four
Number of queues	3

Count Shrikhande is a graph found by S. S. Shrikhande in 1959 ^[1] ^[2] . The graph is strongly regular , has 16 vertices and 48 edges and each vertex has degree 6. Each pair of nodes has exactly two common neighbors, regardless of whether this pair is connected by an edge or not.

Build

The Shrikhande graph can be constructed as the Cayley graph , in which many vertices are $\mathbb {Z} _{4}\times \mathbb {Z} _{4}$ ${\ displaystyle \ mathbb {Z} _ {4} \ times \ mathbb {Z} _ {4}}$ $\mathbb {Z} _{4}\times \mathbb {Z} _{4}$ , and two vertices are connected if and only if the difference is in $\{\pm (1,0),\pm (0,1),\pm (1,1)\}$ ${\ displaystyle \ {\ pm (1,0), \ pm (0,1), \ pm (1,1) \}}$ $\{\pm (1,0),\pm (0,1),\pm (1,1)\}$ .

Properties

In the Shrikhande graph, any two vertices I and J have two different common neighbors (excluding the vertices I and J themselves), which is true regardless of whether I and J are adjacent or not. In other words, the graph is highly regular and its parameters are: {16,6,2,2}, that is $\lambda =\mu =2$ ${\ displaystyle \ lambda = \ mu = 2}$ $\lambda =\mu =2$ . From this equality it follows that the graph is associated with symmetric balanced incomplete block diagrams ( English Balanced Incomplete Block Designs , BIBD). The Shrikhande graph shares these parameters with exactly one other graph, the 4 × 4 rook graph , that is, the edge graph L ( K _4,4 ) of the complete bipartite graph K _4,4 . The last graph is the only edge graph L ( K _{n, n} ) for which strong regularity parameters do not uniquely determine this graph, and the graph divides them with another graph, namely the Shrikhande graph (which is not a rook graph) ^[2] ^[3 ^] ^] .

Count Shrikhande is locally hexagonal . That is, the neighbors of each vertex form a cycle of six vertices. Like any locally cyclic graph, the Shrikhande graph is a Whitney triangulation of some surface. In the case of the Shrikhande graph, this surface is a torus in which each vertex is surrounded by six triangles ^[4] Thus, the Shrikhande graph is a toroidal graph . An embedding forms a regular mapping into a torus with 32 triangular faces. The skeleton of the dual graph of this mapping (as embedded in a torus) is the Dick graph , a cubic symmetric graph.

Count Shrikhande is not remotely transitive . This is the smallest distance-regular graph that is not distance-transitive ^[5] .

The automorphism group of the Shrikhande graph has order 192. It acts transitively on the vertices, on the edges and arcs of the graph. Therefore, the Shrikhande graph is a symmetric graph .

The characteristic polynomial of Count Shrikhande is equal to $(x-6)(x-2)^{6}(x+2)^{9}$ ${\ displaystyle (x-6) (x-2) ^ {6} (x + 2) ^ {9}}$ . Thus, the Shrikhande graph is a whole graph - its spectrum consists entirely of integers.

The graph has a book thickness of 4 and the number of queues 3 ^[6] .

Gallery

Count Shrikhande is toroidal .
The chromatic number of Count Shrikhande is 4.
The chromatic index of the Shrikhande graph is 6.
Count Shrikhande drawn symmetrically.
Count Shrikhande of the Hamilton .

Notes

↑ Weisstein, Eric W. Shrikhande Graph on the Wolfram MathWorld website.
↑ ¹ ² Shrikhande, 1959 , p. 781–798.
↑ Harary, 1972 , p. 79.
↑ Brouwer AE Shrikhande graph .
↑ Brouwer, Cohen, Neumaier, 1989 , p. 104-105, 136.
↑ Wolz, 2018 .

Literature

Shrikhande SS The uniqueness of the L ₂ association scheme // Annals of Mathematical Statistics. - 1959.- T. 30 . - S. 781–798 . - DOI : 10.1214 / aoms / 1177706207 .
Frank Harary. Graph Theory . - Massachusetts: Addison-Wesley, 1972.
- Harari F. Graph Theory. - M .: "The World", 1973.
, ISBN 0-521-43594-3
Brouwer AE, Cohen AM, Neumaier A. Distance-Regular Graphs. - New York: Springer-Verlag, 1989. - S. 104-105, 136.
Jessica Wolz. Engineering Linear Layouts with SAT. - University of Tübingen, 2018. - (Master Thesis).

Links

The Shrikhande Graph , Peter Cameron, August 2010.

[1] Weisstein, Eric W. Shrikhande Graph on the Wolfram MathWorld website.

[_13bbd7fae110bf69-2] ¹ ² Shrikhande, 1959 , p. 781–798.

[_b9200101d4f8f677-3] Harary, 1972 , p. 79.

[4] Brouwer AE Shrikhande graph .

[_f9612bda804e74e3-5] Brouwer, Cohen, Neumaier, 1989 , p. 104-105, 136.

[_3f4963a0713471e0-6] Wolz, 2018 .