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 regarded him 1868. The term Greenwood - Gleason graph is used synonymously.

The graph can be constructed as follows: The nodes in the five-dimensional cube are fixed-length binary representations of integers up, that is, the strings:

"00000 " → 0   "00001 " → 1   " 00010 " → 2 ...   "11111 " → 31 The set of edges of the cube is then the relation with and differ in exactly one point of their representations. This yields the Clebsch graph by identifying antipodal vertices, ie points which are different in all 5 digits.

Properties

The graph is strongly regular. The minimum degree and the maximum degree are equal and have the value, so the graph is not Euler tour. The graph is hamiltonian and non-planar. The Komplementgraph is also strongly regular.

The graph is a Cayleygraph. Its automorphism group has order and is isomorphic to the Coxeter group. The graph is node -, edge-and distanztransitiv.

Planar embeddings

The achromatic number of the Clebsch graph is.

The chromatic number of the Clebsch graph is.

The chromatic index of the Clebsch graph is.