In the mathematical field of graph theory, the odd graphs are a family of symmetric graphs defined from certain set systems. They include and generalize the Petersen graph.

The odd graphs have high odd girth, meaning that they contain long odd-length cycless but no short ones. However their name comes not from this property, but from the fact that each edge in the graph has an "odd man out", an element that does not participate in the two sets connected by the edge.

Definition and examples

has one vertex-element subsets-element set. Two vertices are connected by an edge if and only if the corresponding subsets are disjoint. is the Kneser graph.

is the familiar Petersen graph.

The generalized odd graphs are defined as distance-regular graphs with diameter. They include the odd graphs and the folded cube graphs.

History and applications

Although the Petersen graph has been known since 1898, its definition as an odd graph dates to the work of . 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.

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.

Properties

is regular is

Distance and symmetry

, this is a shortest path.

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. Odd graphs are distance transitive, hence distance regular. As distance-regular graphs, they are uniquely defined by their intersection array: no other distance-regular graphs can have the same parameters as an odd graph. are never Cayley graphs.

Because odd graphs are regular and edge-transitive, their vertex connectivity.

have girth six; however, although they are not bipartite graphs has odd girth distinct eigenvalues are known as the generalized odd graphs, and include the folded cube graphs as well as the odd graphs themselves.

Independent sets and vertex coloring

, they are not disjoint, and form an independent set. It follows from the Erdős–Ko–Rado theorem that these are the maximum independent sets, i.e. the independence number maximum independent sets.

, then the complement. This complementary set induces a matching vertices of the independent set. Because of this decomposition, and because odd graphs are not bipartite, they have chromatic number three: the vertices of the maximum independent set can be assigned a single color, and two more colors suffice to color the complementary matching.

Edge coloring

By Vizing's theorem, the number of colors needed to color the edges is a power of two. colors.

Biggs explains this problem with the following story, about the "footballers of Croam": eleven soccer players in the fictional town of Croam wish to form up pairs of five-man teams provides a solution to the players' scheduling problem.

Hamiltonicity

is a well known non-Hamiltonian are known to have a Hamiltonian cycle. As the odd graphs are vertex-transitive, they are thus one of the special cases with a known positive answer to Lovász' conjecture on Hamiltonian cycles in vertex-transitive graphs. Biggs conjectured. prevents an 8-color edge coloring from existing, but does not rule out the possibility of a partition into four Hamiltonian cycles.

References

External links