Odd graph

In the mathematical field of graph theory, the odd graphs are a family of symmetric graphs with high odd girth, defined from certain set systems. They include and generalize the Petersen graph. The odd graph has one vertex for each of the -element subsets of a -element set. Two vertices are connected by an edge if and only if the corresponding subsets are disjoint. That is, is the Kneser graph . is a triangle, while is the familiar Petersen graph. The generalized odd graphs are defined as distance-regular graphs with diameter and odd girth for some . They include the odd graphs and the folded cube graphs. Although the Petersen graph has been known since 1898, its definition as an odd graph dates to the work of , who also studied the odd graph . Odd graphs have been studied for their applications in chemical graph theory, in modeling the shifts of carbonium ions. They have also been proposed as a network topology in parallel computing. The notation for these graphs was introduced by Norman Biggs in 1972. Biggs and Tony Gardiner explain the name of odd graphs in an unpublished manuscript from 1974: each edge of an odd graph can be assigned the unique element which is the "odd man out", i.e., not a member of either subset associated with the vertices incident to that edge. The odd graph is regular of degree . It has vertices and edges. Therefore, the number of vertices for is If two vertices in correspond to sets that differ from each other by the removal of elements from one set and the addition of different elements, then they may be reached from each other in steps, each pair of which performs a single addition and removal. If , this is a shortest path; otherwise, it is shorter to find a path of this type from the first set to a set complementary to the second, and then reach the second set in one more step. Therefore, the diameter of is . Every odd graph is 3-arc-transitive: every directed three-edge path in an odd graph can be transformed into every other such path by a symmetry of the graph.