Clebsch graph

In graph theory , the Clebsch graph is an undirected graph with 16 nodes and 40 edges. It is named after Alfred Clebsch , who looked at it in 1868. The term Greenwood – Gleason graph is used synonymously.

The graph can be constructed as follows: Let the nodes of the five-dimensional cube be binary representations of the fixed length of the integers from to , i.e. the character strings : ${\displaystyle v_{i}\in V}$ ${\displaystyle 5}$ ${\displaystyle 0}$ ${\displaystyle 2^{5}-1=31}$

 ${\displaystyle v_{0}=}$ "00000" → 0
 ${\displaystyle v_{1}=}$ "00001" → 1
 ${\displaystyle v_{2}=}$ "00010" → 2
...
 ${\displaystyle v_{31}=}$ "11111" → 31

The set of edges of the cube is then the relation with and differ in exactly one place in their representations. The Clebsch graph is obtained from this by identifying antipodal corner points, i.e. points that differ in all 5 places. ${\displaystyle A\subset V\times V}$ ${\displaystyle (x,y)\in A\Leftrightarrow x}$ ${\displaystyle y}$

properties

Graph theoretical properties

The graph is strongly regular . The minimum degree and the maximum degree are the same and have the value , so the graph is not Eulerian . The graph is Hamiltonian and not planar . The complement graph is also strongly regular. ${\displaystyle 5}$

Algebraic properties

The graph is a Cayley graph . Its automorphism group has the order and is isomorphic to the Coxeter group . The graph is node , edge and distance transitive . ${\displaystyle 1920}$ ${\displaystyle D_{5}}$

Planar embeddings

• 

  The Clebsch graph is Hamiltonian .

• 

  The achromatic number of the Clebsch graph is  . ${\displaystyle 8}$

• 

  The chromatic number of the Clebsch graph is  . ${\displaystyle 4}$

• 

  The chromatic index of the Clebsch graph is  . ${\displaystyle 5}$

Individual evidence

1. ↑ A. Clebsch, Ueber the surfaces of the fourth order, which have a double curve of the second degree, J. für Math. 69 (1868) 142-184.
2. ^ The Clebsch Graph at Mathworld