View source for Synchronous frame

{{Infobox graph
 | name = Odd graph
 | image = [[File:Kneser graph KG(5,2).svg|200px]]
 | image_caption = ''O''<sub>3</sub> = KG<sub>5,2</sub> is the Petersen graph
 | namesake = 
 | vertices = <math>\tbinom {2n-1}{n-1}</math>
 | edges = <math>n\tbinom {2n-1}{n-1}/2</math>
 | automorphisms = 
 | radius = 
 | diameter = ''n''&nbsp;&minus;&nbsp;1<ref name="b76">{{citation
 | last = Biggs | first = Norman L.
 | doi = 10.1007/BF00148146
 | issue = 1
 | journal = Geometriae Dedicata
 | pages = 117–127
 | title = Automorphic graphs and the Krein condition
 | volume = 5
 | year = 1976}}.</ref><ref name="b79"/>
 | girth = 3 if ''n'' = 2<br>5 if ''n'' = 3<br>6 if ''n'' > 3<ref>{{citation
 | last = West | first = Douglas B. | author-link = Douglas West (mathematician)
 | contribution = Exercise 1.1.28
 | edition = 2nd
 | location = Englewood Cliffs, NJ
 | page = 17
 | publisher = Prentice-Hall
 | title = Introduction to Graph Theory
 | year = 2000}}.</ref>
 | chromatic_number = 
 | chromatic_index = 
 | properties = [[Distance-transitive graph|Distance-transitive]]
 | notation = ''O<sub>n</sub>''
}}
[[File:Odd graph O4.svg|thumb|360px|The odd graph ''O''<sub>4</sub> = KG<sub>7,3</sub>]]
In the [[mathematics|mathematical]] field of [[graph theory]], the '''odd graphs''' ''O<sub>n</sub>'' are a family of [[symmetric graph]]s with high [[odd girth]], defined from certain [[set system]]s. They include and generalize the [[Petersen graph]].

==Definition and examples==
The odd graph ''O<sub>n</sub>'' has one vertex for each of the (''n''&nbsp;&minus;&nbsp;1)-element subsets of a (2''n''&nbsp;&minus;&nbsp;1)-element set. Two vertices are connected by an edge if and only if the corresponding subsets are [[disjoint (sets)|disjoint]].<ref>{{MathWorld |title=Odd Graph|urlname=OddGraph}}</ref> That is, ''O<sub>n</sub>'' is a [[Kneser graph]] ''KG''(2''n''&nbsp;&minus;&nbsp;1,''n''&nbsp;&minus;&nbsp;1).

''O''<sub>2</sub> is a triangle, while ''O''<sub>3</sub> is the familiar [[Petersen graph]].

The '''generalized odd graphs''' include the odd graphs and the [[folded cube graph]]s, and are defined as [[distance-regular graph]]s with [[diameter (graph theory)|diameter]] ''n''&nbsp;&minus;&nbsp;1 and odd girth 2''n''&nbsp;&minus;&nbsp;1 for some ''n''.<ref name="vdh10"/>

==History and applications==
Although the Petersen graph has been known since 1898, its definition as an odd graph dates to the work of {{harvtxt|Kowalewski|1917}}, who also studied the odd graph ''O''<sub>4</sub>.<ref name="b79"/><ref>{{citation
 | last = Kowalewski | first = A.
 | journal = Sitzungsber. Akad. Wiss. Wien (Abt. IIa)
 | pages = 67–90, 963–1007
 | title = W. R. Hamilton's Dodekaederaufgabe als Buntordnungproblem
 | volume = 126
 | year = 1917}}. As cited by {{harvtxt|Biggs|1979}}.</ref>
Odd graphs have been studied for their applications in [[chemical graph theory]], in modeling the shifts of [[carbonium ion]]s.<ref>{{citation
 | last1 = Balaban | first1 = Alexandru T.
 | last2 = Fǎrcaşiu | first2 = D.
 | last3 = Bǎnicǎ | first3 = R.
 | journal = Rev. Roum. Chim.
 | page = 1205
 | title = Graphs of multiple 1, 2-shifts in carbonium ions and related systems
 | volume = 11
 | year = 1966}}.</ref><ref name="bal72"/> They have also been proposed as a [[network topology]] in [[parallel computing]].<ref>{{citation
 | last1 = Ghafoor | first1 = Arif
 | last2 = Bashkow | first2 = Theodore R.
 | doi = 10.1109/12.73594
 | issue = 2
 | journal = IEEE Transactions on Computing
 | pages = 225–232
 | title = A study of odd graphs as fault-tolerant interconnection networks
 | volume = 40
 | year = 1991}}.</ref>

The notation ''O<sub>n</sub>'' for these graphs was introduced by [[Norman Biggs (mathematician)|Norman Biggs]] in 1972.<ref name="b72">{{citation
 | last = Biggs | first = Norman
 | contribution = An edge-colouring problem
 | edition = 9
 | editor-last = Guy | editor-first = Richard K. | editor-link = Richard K. Guy
 | journal = American Mathematical Monthly
 | pages = 1018–1020
 | title = Research Problems
 | jstor = 2318076
 | volume = 79
 | year = 1972}}.</ref> 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 of ''X'' which is the "[[wiktionary:odd one out|odd man out]]", i.e., not a member of  either subset associated with the vertices incident to that edge.<ref>{{citation
 | last1 = Brouwer | first1 = Andries | author1-link = Andries Brouwer
 | last2 = Cohen | first2 = Arjeh M.
 | last3 = Neumaier | first3 = A.
 | isbn = 0-387-50619-5
 | title = Distance-regular Graphs
 | year = 1989}}.</ref><ref>{{citation
 | last = Ed Pegg | first = Jr. | author-link = Ed Pegg, Jr.
 | date = December 29, 2003
 | publisher = [[Mathematical Association of America]]
 | series = Math Games
 | title = Cubic Symmetric Graphs
 | url = http://maa.org/editorial/mathgames/mathgames_12_29_03.html}}.</ref>

==Properties==
The odd graph ''O''<sub>''n''</sub> is regular of degree ''n''. It has <math>\tbinom {2n-1}{n-1}</math> vertices and <math>n\tbinom {2n-1}{n-1}/2</math> edges. Therefore, the number of vertices for ''n'' = 1, 2,... is
:1, 3, 10, 35, 126, 462, 1716, 6435 {{OEIS|A001700}}.

===Distance and symmetry===
If two vertices in ''O''<sub>''n''</sub> correspond to sets that differ from each other by the removal of ''k'' elements from one set and the addition of ''k'' different elements, then they may be reached from each other in 2''k'' steps, each pair of which performs a single addition and removal. If 2''k''&nbsp;<&nbsp;''n'', 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 (graph theory)|diameter]] of ''O''<sub>''n''</sub> is ''n''&nbsp;&minus;&nbsp;1.<ref name="b76"/><ref name="b79"/>

Every odd graph is [[Symmetric graph|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.<ref>{{citation|first=László|last=Babai|authorlink=László Babai|contribution=Automorphism groups, isomorphism, reconstruction|id=Proposition 1.9|title=Handbook of Combinatorics|url=http://www.cs.uchicago.edu/files/tr_authentic/TR-94-10.ps|pages=1447–1540|editor1-first=Ronald L.|editor1-last=Graham|editor1-link=Ronald Graham|editor2-first=Martin|editor2-last=Grötschel|editor3-first=László|editor3-last=Lovász|editor3-link=László Lovász|volume=I|publisher=North-Holland|year=1995}}.</ref>
Odd graphs are [[Distance-transitive graph|distance transitive]], hence [[Distance-regular graph|distance regular]].<ref name="b79"/> 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.<ref>{{citation
 | last = Moon | first = Aeryung
 | doi = 10.1016/0012-365X(82)90057-7
 | issue = 1
 | journal = Discrete Mathematics
 | pages = 91–97
 | title = Characterization of the odd graphs ''O<sub>k</sub>'' by parameters
 | volume = 42
 | year = 1982}}.</ref> However, despite their high degree of symmetry, the odd graphs ''O<sub>n</sub>'' for ''n''&nbsp;>&nbsp;2 are never [[Cayley graph]]s.<ref>{{citation
 | last = Godsil | first = C. D.
 | doi = 10.1016/0012-365X(80)90055-2
 | issue = 2
 | journal = Discrete Mathematics
 | pages = 205–207
 | title = More odd graph theory
 | volume = 32
 | year = 1980}}.</ref>

Odd graphs with ''n'' ≥ 3 have [[girth (graph theory)|girth]] six; however, although they are not [[bipartite graph]]s, their odd cycles are much longer. Specifically, the odd graph ''O<sub>n</sub>'' has [[odd girth]] 2''n''&nbsp;&minus;&nbsp;1. If a ''n''-regular graph has diameter ''n''&nbsp;&minus;&nbsp;1 and odd girth 2''n''&nbsp;&minus;&nbsp;1, and has only ''n'' distinct [[eigenvalue]]s, it must be distance-regular. Distance-regular graphs with diameter ''n''&nbsp;&minus;&nbsp;1 and odd girth 2''n''&nbsp;&minus;&nbsp;1 are known as the '''generalized odd graphs''', and include the [[folded cube graph]]s as well as the odd graphs themselves.<ref name="vdh10">{{citation
 | last1 = Van Dam | first1 = Edwin
 | last2 = Haemers | first2 = Willem H.
 | series = CentER Discussion Paper Series No. 2010-47
 | title = An Odd Characterization of the Generalized Odd Graphs
 | ssrn = 1596575
 | year = 2010}}.</ref>

===Independent sets and vertex coloring===
Let ''O<sub>n</sub>'' be an odd graph defined from the subsets of a (2''n''&nbsp;&minus;&nbsp;1)-element set ''X'', and let ''x'' be any member of ''X''. Then, among the vertices of  ''O<sub>n</sub>'', exactly <math>\tbinom{2n-2}{n-2}</math> vertices correspond to sets that contain&nbsp;''x''. Because all these sets contain ''x'', they are not disjoint, and form an [[independent set]] of  ''O<sub>n</sub>''. That is, ''O<sub>n</sub>'' has 2''n''&nbsp;&minus;&nbsp;1 different independent sets of size <math>\tbinom{2n-2}{n-2}</math>. It follows from the [[Erdős–Ko–Rado theorem]] that these are the [[maximum independent set]]s of ''O<sub>n</sub>''. that is, the [[independence number]] of ''O<sub>n</sub>'' is <math>\tbinom{2n-2}{n-2}.</math> Further, every maximum independent set must have this form, so ''O<sub>n</sub>'' has exactly 2''n''&nbsp;&minus;&nbsp;1 maximum independent sets.<ref name="b79">{{citation|contribution=Some odd graph theory|first=Norman|last=Biggs|series=Annals of the New York Academy of Sciences|volume=319|title=Second International Conference on Combinatorial Mathematics|pages=71–81|year=1979|doi=10.1111/j.1749-6632.1979.tb32775.x}}.</ref>

If ''I'' is a maximum independent set, formed by the sets that contain ''x'', then the [[complement (set theory)|complement]] of ''I'' is the set of vertices that do not contain ''x''. This complementary set [[induced subgraph|induces]] a [[matching (graph theory)|matching]] in ''G''. Each vertex of the independent set is adjacent to ''n'' vertices of the matching, and each vertex of the matching is adjacent to ''n''&nbsp;&minus;&nbsp;1 vertices of the independent set.<ref name="b79"/> 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 [[edge coloring|color the edges]] of the odd graph ''O''<sub>''n''</sub> is either ''n'' or ''n''&nbsp;+&nbsp;1, and in the case of the Petersen graph  ''O''<sub>3</sub> it is ''n''&nbsp;+&nbsp;1. When ''n'' is a power of two, the number of vertices in the graph is odd, from which it again follows that the number of edge colors is ''n''&nbsp;+&nbsp;1.<ref name="el73">{{citation
 | last1 = Meredith | first1 = Guy H. J.
 | last2 = Lloyd | first2 = E. Keith
 | doi = 10.1016/0095-8956(73)90016-6
 | journal = Journal of Combinatorial Theory, Series B
 | pages = 161–166
 | title = The footballers of Croam
 | volume = 15
 | year = 1973}}.</ref> However, ''O''<sub>5</sub>, ''O''<sub>6</sub>, and ''O''<sub>7</sub> can each be edge-colored with ''n'' colors.<ref name="b79"/><ref name="el73"/>

Biggs<ref name="b72"/> explains this problem with the following story: eleven [[soccer]] players in the fictional town of Croam wish to form up pairs of [[Five-a-side football|five-man teams]] (with an odd man out to serve as referee) in all 1386 possible ways, and they wish to schedule the games between each pair in such a way that the six games for each team are played on six different days of the week, with Sundays off for all teams. Is it possible to do so? In this story, each game represents an edge of ''O''<sub>6</sub>, each weekday is represented by a color, and a 6-color edge coloring of ''O''<sub>6</sub> provides a solution to the players' scheduling problem.

===Hamiltonicity===
The Petersen graph ''O''<sub>3</sub> is a well known non-Hamiltonian graph, but ''O''<sub>4</sub> through ''O''<sub>14</sub> have been shown to contain [[Hamiltonian cycle]]s.<ref name="bal72">{{citation
 | last = Balaban | first = Alexandru T.
 | journal = Rev. Roumaine Math. Pures Appl.
 | pages = 3–16
 | title = Chemical graphs, Part XIII: Combinatorial patterns
 | volume = 17
 | year = 1972}}.</ref><ref>{{citation
 | last1 = Meredith | first1 = Guy H. J.
 | last2 = Lloyd | first2 = E. Keith
 | contribution = The Hamiltonian graphs ''O''<sub>4</sub> to ''O''<sub>7</sub>
 | location = Southend
 | pages = 229–236
 | publisher = Inst. Math. Appl.
 | title = Combinatorics (Proc. Conf. Combinatorial Math., Math. Inst., Oxford, 1972)
 | year = 1972}}.</ref><ref>{{citation
 | last = Mather | first = Michael
 | doi = 10.1016/0095-8956(76)90066-6
 | journal = Journal of Combinatorial Theory, Series B
 | pages = 62–63
 | title = The Rugby footballers of Croam
 | volume = 20
 | year = 1976}}.</ref><ref>{{citation
 | last1 = Shields | first1 = Ian
 | last2 = Savage | first2 = Carla D. | author2-link = Carla Savage
 | journal = Bulletin of the Institute for Combinatorics and Its Applications
 | pages = 13–22
 | title = A note on Hamilton cycles in Kneser graphs
 | url = http://www.cybershields.com/publications/kneser3.pdf
 | volume = 40
 | year = 2004}}.</ref> More strongly, combining the Hamiltonian cycle and edge coloring problems, it is possible to partition the edges of ''O''<sub>''n''</sub> (for ''n'' = 4, 5, 6, 7) into floor(''n''/2) Hamiltonian cycles; when ''n'' is odd, the leftover edges form a perfect matching.<ref name="b79"/><ref name="el73"/> For ''n''&nbsp;=&nbsp;8, the odd number of vertices in ''O''<sub>''n''</sub> prevents an 8-color edge coloring from existing, but does not rule out the possibility of a partition into four Hamiltonian cycles.

The [[Lovász conjecture]] implies that every odd graph has a Hamiltonian path and that every odd graph ''O<sub>n</sub>'' with ''n''&nbsp;≥&nbsp;4 has a Hamiltonian cycle.

==References==
{{reflist}}

[[Category:Parametric families of graphs]]
[[Category:Regular graphs]]