Odd graphs

The Odd graph on a (2m+1)-set X, denoted by O_m+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 S_2m+1 with point stabilizer S_m×S_m+1.

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

Small examples:

O₁ is a loop on a single vertex.

O₂ is K₃, the triangle. Intersection array {2;1}.

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

O₄, on 35 vertices, has intersection array {4,3,3;1,1,2} and spectrum 4¹ 2¹⁴ (-1)¹⁴ (-3)⁶. It is found as subgraph of the Hoffman-Singleton graph, the M₂₂ graph, the O^-₆(3) graph, and the McL graph. It contains the Coxeter graph.

References

[BCN], Section 9.1D.