Clebsch graph

Alfred Clebsch (1833-1872) was a pioneer in algebraic geometry.

The Clebsch graph named after him is the unique strongly regular graph with parameters v = 16, k = 10, λ = 6, μ = 6. It is the halved 5-cube, and hence is cubelike. It is the local graph of the Schläfli graph.

The complement of the Clebsch graph is the unique strongly regular graph with parameters v = 16, k = 5, λ = 0, μ = 2. It is the folded 5-cube. The subgraph on the non-neighbours of a point is the Petersen graph.

Independence and chromatic number

The Clebsch graph has independence number 2 and chromatic number 8. The complement of the Clebsch graph has independence number 5 and chromatic number 4.

References

A. Clebsch, Ueber die Flächen vierter Ordnung, welche eine Doppelcurve zweiten Grades besitzen, J. für Math. 69 (1868) 142-184.

H.S.M. Coxeter, Self-dual configurations and regular graphs, Bull. Amer. Math. Soc. 56 (1950) 413-455.

W.H. Clatworthy, Partially balanced incomplete block designs with two associate classes and two treatments per block, J. Res. Nat. Bur. Standards 54 (1955) 177-190.

J.J. Seidel, Strongly regular graphs with (-1,1,0) adjacency matrix having eigenvalue 3, Lin. Alg. Appl. 1 (1968) 281-298.