Odd graphs

The Odd graph on a (2m+1)-set X, denoted by Om+1 (the subscript gives the valency), is the graph on the m-subsets of this (2m+1)-set, where disjoint m-subsets are adjacent.

This name is due to Biggs & Gardiner, who explain the name by since each edge can be assigned the unique element of X which is not a member of either vertex incident with that edge - the "odd man out".

The Odd graphs are distance-regular (of diameter m), and uniquely characterized by their intersection array. Their automorphism group is S2m+1 with point stabilizer Sm×Sm+1.

Odd graphs are Kneser graphs. One has Om+1 = K(2m+1,m).

Small examples:

O1 is a loop on a single vertex.

O2 is K3, the triangle. Intersection array {2;1}.

O3 is the Petersen graph. Intersection array {3,2;1,1}.

O4, on 35 vertices, has intersection array {4,3,3;1,1,2} and spectrum 41 214 (-1)14 (-3)6. It is found as subgraph of the Hoffman-Singleton graph, the M22 graph, the O-6(3) graph, and the McL graph. It contains the Coxeter graph.


[BCN], Section 9.1D.