Odd graph

Odd graph
The Petersen graph as an odd graph O_{3}Vertices Edges Diameter n − 1^{[1]}^{[2]} Girth 3 if n = 2
5 if n = 3
6 if n > 3^{[3]}Properties Distancetransitive Notation O_{n} v · In the mathematical field of graph theory, the odd graphs O_{n} are a family of symmetric graphs with high odd girth, defined from certain set systems. They include and generalize the Petersen graph.
Contents
Definition and examples
The odd graph O_{n} has one vertex for each of the (n − 1)element subsets of a (2n − 1)element set. Two vertices are connected by an edge if and only if the corresponding subsets are disjoint.^{[4]} That is, O_{n} is a Kneser graph KG(2n − 1,n − 1).
O_{2} is a triangle, while O_{3} is the familiar Petersen graph.
The generalized odd graphs include the odd graphs and the folded cube graphs, and are defined as distanceregular graphs with diameter n − 1 and odd girth 2n − 1 for some n.^{[5]}
History and applications
Although the Petersen graph has been known since 1898, its definition as an odd graph dates to the work of Kowalewski (1917), who also studied the odd graph O_{4}.^{[2]}^{[6]} Odd graphs have been studied for their applications in chemical graph theory, in modeling the shifts of carbonium ions.^{[7]}^{[8]} They have also been proposed as a network topology in parallel computing.^{[9]}
The notation O_{n} for these graphs was introduced by Norman Biggs in 1972.^{[10]} Biggs and Anthony 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 "odd man out", i.e., not a member of either subset associated with the vertices incident to that edge.^{[11]}^{[12]}
Properties
The odd graph O_{n} is regular of degree n. It has vertices and edges. Therefore, the number of vertices for n = 1, 2,... is
Distance and symmetry
If two vertices in O_{n} 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 2k steps, each pair of which performs a single addition and removal. If 2k < 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 of O_{n} is n − 1.^{[1]}^{[2]}
Every odd graph is 3arctransitive: every directed threeedge path in an odd graph can be transformed into every other such path by a symmetry of the graph.^{[13]} Odd graphs are distance transitive, hence distance regular.^{[2]} As distanceregular graphs, they are uniquely defined by their intersection array: no other distanceregular graphs can have the same parameters as an odd graph.^{[14]} However, despite their high degree of symmetry, the odd graphs O_{n} for n > 2 are never Cayley graphs.^{[15]}
Odd graphs with n ≥ 3 have girth six; however, although they are not bipartite graphs, their odd cycles are much longer. Specifically, the odd graph O_{n} has odd girth 2n − 1. If a nregular graph has diameter n − 1 and odd girth 2n − 1, and has only n distinct eigenvalues, it must be distanceregular. Distanceregular graphs with diameter n − 1 and odd girth 2n − 1 are known as the generalized odd graphs, and include the folded cube graphs as well as the odd graphs themselves.^{[5]}
Independent sets and vertex coloring
Let O_{n} be an odd graph defined from the subsets of a (2n − 1)element set X, and let x be any member of X. Then, among the vertices of O_{n}, exactly vertices correspond to sets that contain x. Because all these sets contain x, they are not disjoint, and form an independent set of O_{n}. That is, O_{n} has 2n − 1 different independent sets of size . It follows from the Erdős–Ko–Rado theorem that these are the maximum independent sets of O_{n}. that is, the independence number of O_{n} is Further, every maximum independent set must have this form, so O_{n} has exactly 2n − 1 maximum independent sets.^{[2]}
If I is a maximum independent set, formed by the sets that contain x, then the complement of I is the set of vertices that do not contain x. This complementary set induces a 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 − 1 vertices of the independent set.^{[2]} 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 of the odd graph O_{n} is either n or n + 1, and in the case of the Petersen graph O_{3} it is n + 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 + 1.^{[16]} However, O_{5}, O_{6}, and O_{7} can each be edgecolored with n colors.^{[2]}^{[16]}
Biggs^{[10]} explains this problem with the following story: eleven soccer players in the fictional town of Croam wish to form up pairs of fiveman 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_{6}, each weekday is represented by a color, and a 6color edge coloring of O_{6} provides a solution to the players' scheduling problem.
Hamiltonicity
The Petersen graph O_{3} is a well known nonHamiltonian graph, but O_{4} through O_{14} have been shown to contain Hamiltonian cycles.^{[8]}^{[17]}^{[18]}^{[19]} More strongly, combining the Hamiltonian cycle and edge coloring problems, it is possible to partition the edges of O_{n} (for n = 4, 5, 6, 7) into floor(n/2) Hamiltonian cycles; when n is odd, the leftover edges form a perfect matching.^{[2]}^{[16]} For n = 8, the odd number of vertices in O_{n} prevents an 8color 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_{n} with n ≥ 4 has a Hamiltonian cycle.
References
 ^ ^{a} ^{b} Biggs, Norman L. (1976), "Automorphic graphs and the Krein condition", Geometriae Dedicata 5 (1): 117–127, doi:10.1007/BF00148146 .
 ^ ^{a} ^{b} ^{c} ^{d} ^{e} ^{f} ^{g} ^{h} Biggs, Norman (1979), "Some odd graph theory", Second International Conference on Combinatorial Mathematics, Annals of the New York Academy of Sciences, 319, pp. 71–81, doi:10.1111/j.17496632.1979.tb32775.x .
 ^ West, Douglas B. (2000), "Exercise 1.1.28", Introduction to Graph Theory (2nd ed.), Englewood Cliffs, NJ: PrenticeHall, p. 17 .
 ^ Weisstein, Eric W., "Odd Graph" from MathWorld.
 ^ ^{a} ^{b} Van Dam, Edwin; Haemers, Willem H. (2010), An Odd Characterization of the Generalized Odd Graphs, CentER Discussion Paper Series No. 201047, SSRN 1596575 .
 ^ Kowalewski, A. (1917), "W. R. Hamilton's Dodekaederaufgabe als Buntordnungproblem", Sitzungsber. Akad. Wiss. Wien (Abt. IIa) 126: 67–90, 963–1007 . As cited by Biggs (1979).
 ^ Balaban, Alexandru T.; Fǎrcaşiu, D.; Bǎnicǎ, R. (1966), "Graphs of multiple 1, 2shifts in carbonium ions and related systems", Rev. Roum. Chim. 11: 1205 .
 ^ ^{a} ^{b} Balaban, Alexandru T. (1972), "Chemical graphs, Part XIII: Combinatorial patterns", Rev. Roumaine Math. Pures Appl. 17: 3–16 .
 ^ Ghafoor, Arif; Bashkow, Theodore R. (1991), "A study of odd graphs as faulttolerant interconnection networks", IEEE Transactions on Computing 40 (2): 225–232, doi:10.1109/12.73594 .
 ^ ^{a} ^{b} Biggs, Norman (1972), An edgecolouring problem, in Guy, Richard K., "Research Problems", American Mathematical Monthly 79: 1018–1020, JSTOR 2318076 .
 ^ Brouwer, Andries; Cohen, Arjeh M.; Neumaier, A. (1989), Distanceregular Graphs, ISBN 0387506195 .
 ^ Ed Pegg, Jr. (December 29, 2003), Cubic Symmetric Graphs, Math Games, Mathematical Association of America, http://maa.org/editorial/mathgames/mathgames_12_29_03.html .
 ^ Babai, László (1995), "Automorphism groups, isomorphism, reconstruction", in Graham, Ronald L.; Grötschel, Martin; Lovász, László, Handbook of Combinatorics, I, NorthHolland, pp. 1447–1540, Proposition 1.9, http://www.cs.uchicago.edu/files/tr_authentic/TR9410.ps .
 ^ Moon, Aeryung (1982), "Characterization of the odd graphs O_{k} by parameters", Discrete Mathematics 42 (1): 91–97, doi:10.1016/0012365X(82)900577 .
 ^ Godsil, C. D. (1980), "More odd graph theory", Discrete Mathematics 32 (2): 205–207, doi:10.1016/0012365X(80)900552 .
 ^ ^{a} ^{b} ^{c} Meredith, Guy H. J.; Lloyd, E. Keith (1973), "The footballers of Croam", Journal of Combinatorial Theory, Series B 15: 161–166, doi:10.1016/00958956(73)900166 .
 ^ Meredith, Guy H. J.; Lloyd, E. Keith (1972), "The Hamiltonian graphs O_{4} to O_{7}", Combinatorics (Proc. Conf. Combinatorial Math., Math. Inst., Oxford, 1972), Southend: Inst. Math. Appl., pp. 229–236 .
 ^ Mather, Michael (1976), "The Rugby footballers of Croam", Journal of Combinatorial Theory, Series B 20: 62–63, doi:10.1016/00958956(76)900666 .
 ^ Shields, Ian; Savage, Carla D. (2004), "A note on Hamilton cycles in Kneser graphs", Bulletin of the Institute for Combinatorics and Its Applications 40: 13–22, http://www.cybershields.com/publications/kneser3.pdf .
Categories: Parametric families of graphs
 Regular graphs
Wikimedia Foundation. 2010.
Look at other dictionaries:
Graph homomorphism — Not to be confused with graph homeomorphism. In the mathematical field of graph theory a graph homomorphism is a mapping between two graphs that respects their structure. More concretely it maps adjacent vertices to adjacent vertices. Contents 1… … Wikipedia
Graph coloring — A proper vertex coloring of the Petersen graph with 3 colors, the minimum number possible. In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called colors to elements of a graph… … Wikipedia
graph theory — Math. the branch of mathematics dealing with linear graphs. [1965 70] * * * Mathematical theory of networks. A graph consists of nodes (also called points or vertices) and edges (lines) connecting certain pairs of nodes. An edge that connects a… … Universalium
Graph factorization — Not to be confused with Factor graph. 1 factorization of Desargues graph: each color class is a 1 factor … Wikipedia
Kneser graph — infobox graph name = Kneser graph image caption = The Kneser graph KG 5,2, isomorphic to the Petersen graph namesake = Martin Kneser properties = arc transitiveIn graph theory, the Kneser graph KG {n,k} is the graph whose vertices correspond to… … Wikipedia
Glossary of graph theory — Graph theory is a growing area in mathematical research, and has a large specialized vocabulary. Some authors use the same word with different meanings. Some authors use different words to mean the same thing. This page attempts to keep up with… … Wikipedia
Distanceregular graph — Graph families defined by their automorphisms distance transitive distance regular strongly regular … Wikipedia
Perfect graph — The Paley graph of order 9, colored with three colors and showing a clique of three vertices. In this graph and each of its induced subgraphs the chromatic number equals the clique number, so it is a perfect graph. In graph theory, a perfect… … Wikipedia
Clawfree graph — A claw In graph theory, an area of mathematics, a claw free graph is a graph that does not have a claw as an induced subgraph. A claw is another name for the complete bipartite graph K1,3 (that is, a star graph with three edges, three leaves, and … Wikipedia
Degree (graph theory) — A graph with vertices labeled by degree In graph theory, the degree (or valency) of a vertex of a graph is the number of edges incident to the vertex, with loops counted twice.[1] The degree of a vertex … Wikipedia
© Academic, 20002020Share the article and excerpts
We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.
Odd graph

Odd graph
The Petersen graph as an odd graph O_{3}Vertices Edges Diameter n − 1^{[1]}^{[2]} Girth 3 if n = 2
5 if n = 3
6 if n > 3^{[3]}Properties Distancetransitive Notation O_{n}