In the

mathematical Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...

field of

graph theory In mathematics, graph theory is the study of '' graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...

, the Shrikhande graph is a

named graph Named graphs are a key concept of Semantic Web architecture in which a set of Resource Description Framework statements (a graph) are identified using a URI, allowing descriptions to be made of that set of statements such as context, provenance ...

discovered by S. S. Shrikhande in 1959.. It is a

strongly regular graph In graph theory, a strongly regular graph (SRG) is defined as follows. Let be a regular graph with vertices and degree . is said to be strongly regular if there are also integers and such that: * Every two adjacent vertices have comm ...

with 16 vertices and 48 edges, with each vertex having

degree Degree may refer to: As a unit of measurement * Degree (angle), a unit of angle measurement ** Degree of geographical latitude ** Degree of geographical longitude * Degree symbol (°), a notation used in science, engineering, and mathemati ...

6. Every pair of nodes has exactly two other neighbors in common, whether the pair of nodes is connected or not.

Construction

The Shrikhande graph can be constructed as a

Cayley graph In mathematics, a Cayley graph, also known as a Cayley color graph, Cayley diagram, group diagram, or color group is a graph that encodes the abstract structure of a group. Its definition is suggested by Cayley's theorem (named after Arthur Ca ...

. The vertex set is

\mathbb_4 \times \mathbb_4

. Two vertices are adjacent if and only if the difference is in

\

Properties

In the Shrikhande graph, any two vertices ''I'' and ''J'' have two distinct neighbors in common (excluding the two vertices ''I'' and ''J'' themselves), which holds true whether or not ''I'' is adjacent to ''J''. In other words, it is strongly regular and its parameters are: , i.e.,

\lambda = \mu = 2

. This equality implies that the graph is associated with a

symmetric Symmetry (from grc, συμμετρία "agreement in dimensions, due proportion, arrangement") in everyday language refers to a sense of harmonious and beautiful proportion and balance. In mathematics, "symmetry" has a more precise definit ...

BIBD. The Shrikhande graph shares these parameters with exactly one other graph, the 4×4

rook's graph In graph theory, a rook's graph is a graph that represents all legal moves of the rook chess piece on a chessboard. Each vertex of a rook's graph represents a square on a chessboard, and each edge connects two squares on the same row (rank) or on ...

, i.e., the

line graph In the mathematical discipline of graph theory, the line graph of an undirected graph is another graph that represents the adjacencies between edges of . is constructed in the following way: for each edge in , make a vertex in ; for every ...

''L''(''K''_4,4) of the

complete bipartite graph In the mathematical field of graph theory, a complete bipartite graph or biclique is a special kind of bipartite graph where every vertex of the first set is connected to every vertex of the second set..Electronic edition page 17. Graph theory ...

''K''_4,4. The latter graph is the only line graph ''L''(''K_n,n'') for which the strong regularity parameters do not determine that graph uniquely but are shared with a different graph, namely the Shrikhande graph (which is not a rook's graph). The Shrikhande graph is locally hexagonal; that is, the neighbors of each vertex form a cycle of six vertices. As with any locally cyclic graph, the Shrikhande graph is the 1-skeleton of a Whitney triangulation of some surface; in the case of the Shrikhande graph, this surface is a

torus In geometry, a torus (plural tori, colloquially donut or doughnut) is a surface of revolution generated by revolving a circle in three-dimensional space about an axis that is coplanar with the circle. If the axis of revolution does not ...

in which each vertex is surrounded by six triangles. Thus, the Shrikhande graph is a

toroidal graph In the mathematical field of graph theory, a toroidal graph is a graph that can be embedded on a torus. In other words, the graph's vertices can be placed on a torus such that no edges cross. Examples Any graph that can be embedded in a plane ...

. The embedding forms a regular map in the torus, with 32 triangular faces. The skeleton of the dual of this map (as embedded in the torus) is the

Dyck graph In the mathematical field of graph theory, the Dyck graph is a 3- regular graph with 32 vertices and 48 edges, named after Walther von Dyck. It is Hamiltonian with 120 distinct Hamiltonian cycles. It has chromatic number 2, chromatic index ...

, a cubic symmetric graph. The Shrikhande graph is not a

distance-transitive graph In the mathematical field of graph theory, a distance-transitive graph is a graph such that, given any two vertices and at any distance , and any other two vertices and at the same distance, there is an automorphism of the graph that carri ...

. It is the smallest

distance-regular graph In the mathematical field of graph theory, a distance-regular graph is a regular graph such that for any two vertices and , the number of vertices at distance from and at distance from depends only upon , , and the distance between and . ...

that is not distance-transitive. The

automorphism group In mathematics, the automorphism group of an object ''X'' is the group consisting of automorphisms of ''X'' under composition of morphisms. For example, if ''X'' is a finite-dimensional vector space, then the automorphism group of ''X'' is th ...

of the Shrikhande graph is of order 192. It acts transitively on the vertices, on the edges and on the arcs of the graph. Therefore, the Shrikhande graph is a

symmetric graph In the mathematical field of graph theory, a graph is symmetric (or arc-transitive) if, given any two pairs of adjacent vertices and of , there is an automorphism :f : V(G) \rightarrow V(G) such that :f(u_1) = u_2 and f(v_1) = v_2. In ot ...

. The

characteristic polynomial In linear algebra, the characteristic polynomial of a square matrix is a polynomial which is invariant under matrix similarity and has the eigenvalues as roots. It has the determinant and the trace of the matrix among its coefficients. The ...

of the Shrikhande graph is :

(x-6)(x-2)^6(x+2)^9

. Therefore, the Shrikhande graph is an

integral graph In the mathematical field of graph theory, an integral graph is a graph whose adjacency matrix's spectrum consists entirely of integers. In other words, a graph is an integral graph if all of the roots of the characteristic polynomial of its adjace ...

: its

spectrum A spectrum (plural ''spectra'' or ''spectrums'') is a condition that is not limited to a specific set of values but can vary, without gaps, across a continuum. The word was first used scientifically in optics to describe the rainbow of color ...

consists entirely of integers. It has

book thickness In graph theory, a book embedding is a generalization of planar embedding of a graph to embeddings into a ''book'', a collection of half-planes all having the same line as their boundary. Usually, the vertices of the graph are required to lie o ...

4 and

queue number In the mathematical field of graph theory, the queue number of a graph is a graph invariant defined analogously to stack number (book thickness) using first-in first-out (queue) orderings in place of last-in first-out (stack) orderings. Defin ...

3.Jessica Wolz, ''Engineering Linear Layouts with SAT''. Master Thesis, University of Tübingen, 2018

Gallery

Image:Shrikhande torus.svg, The Shrikhande graph is a

. Image:Shrikhande graph 4COL.svg , The

chromatic number In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices o ...

of the Shrikhande graph is 4. Image:Shrikhande graph 6color edge.svg , The

chromatic index In graph theory, an edge coloring of a graph is an assignment of "colors" to the edges of the graph so that no two incident edges have the same color. For example, the figure to the right shows an edge coloring of a graph by the colors red, blue ...

of the Shrikhande graph is 6. Image:Shrikhande graph symmetrical.svg, The Shrikhande graph drawn symmetrically. File:Shrikhande Lombardi.svg, The Shrikhande graph is Hamiltonian.

Notes

References

*{{citation, first1=D. A., last1=Holton, first2=J., last2=Sheehan, title=The Petersen Graph, title-link= The Petersen Graph , publisher=

Cambridge University Press Cambridge University Press is the university press of the University of Cambridge. Granted letters patent by Henry VIII of England, King Henry VIII in 1534, it is the oldest university press in the world. It is also the King's Printer. Cambr ...

, year=1993, isbn=0-521-43594-3, page=270.

External links

The Shrikhande Graph
Peter Cameron, August 2010. Individual graphs Regular graphs Strongly regular graphs