Odd graph

Last updated
Odd graph
Kneser graph KG(5,2).svg
is the Petersen graph
Vertices
Edges
Diameter [1] [2]
Girth 3 for
5 for
6 otherwise [3]
Properties Distance-transitive
NotationOn
Table of graphs and parameters
The odd graph
O
4
=
K
G
(
7
,
3
)
{\displaystyle O_{4}=KG(7,3)} Odd graph O4.svg
The odd graph

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.

Contents

The odd graphs have high odd girth, meaning that they contain long odd-length cycles 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

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. [2] 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 . [4] 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 Kowalewski (1917), who also studied the odd graph . [2] [5] Odd graphs have been studied for their applications in chemical graph theory, in modeling the shifts of carbonium ions. [6] [7] They have also been proposed as a network topology in parallel computing. [8]

The notation for these graphs was introduced by Norman Biggs in 1972. [9] 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. [10] [11]

Properties

The odd graph is regular of degree . It has vertices and edges. Therefore, the number of vertices for is

1, 3, 10, 35, 126, 462, 1716, 6435 (sequence A001700 in the OEIS).

Distance and symmetry

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 . [1] [2]

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. [12] Odd graphs are distance transitive, hence distance regular. [2] 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. [13] However, despite their high degree of symmetry, the odd graphs for are never Cayley graphs. [14]

Because odd graphs are regular and edge-transitive, their vertex connectivity equals their degree, . [15]

Odd graphs with have girth six; however, although they are not bipartite graphs, their odd cycles are much longer. Specifically, the odd graph has odd girth . If an -regular graph has diameter and odd girth , and has only distinct eigenvalues, it must be distance-regular. Distance-regular graphs with diameter and odd girth are known as the generalized odd graphs, and include the folded cube graphs as well as the odd graphs themselves. [4]

Independent sets and vertex coloring

Let be an odd graph defined from the subsets of a -element set , and let be any member of . Then, among the vertices of , exactly vertices correspond to sets that contain . Because all these sets contain , they are not disjoint, and form an independent set of . That is, has different independent sets of size . It follows from the Erdős–Ko–Rado theorem that these are the maximum independent sets of , i.e. the independence number of is Further, every maximum independent set must have this form, so has exactly maximum independent sets. [2]

If is a maximum independent set, formed by the sets that contain , then the complement of is the set of vertices that do not contain . This complementary set induces a matching in . Each vertex of the independent set is adjacent to vertices of the matching, and each vertex of the matching is adjacent to 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 is either or , and in the case of the Petersen graph it is . When 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 . [16] However, , , and can each be edge-colored with colors. [2] [16]

Biggs [9] explains this problem with the following story: eleven soccer players in the fictional town of Croam wish to form up pairs of 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 , each weekday is represented by a color, and a 6-color edge coloring of provides a solution to the players' scheduling problem.

Hamiltonicity

The Petersen graph is a well known non-Hamiltonian graph, but all odd graphs for are known to have a Hamiltonian cycle. [17] 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 [2] conjectured more generally that the edges of can be partitioned into edge-disjoint Hamiltonian cycles. When is odd, the leftover edges must then form a perfect matching. This stronger conjecture was verified for . [2] [16] For , the odd number of vertices in prevents an 8-color edge coloring from existing, but does not rule out the possibility of a partition into four Hamiltonian cycles.

Related Research Articles

<span class="mw-page-title-main">Petersen graph</span> Cubic graph with 10 vertices and 15 edges

In the mathematical field of graph theory, the Petersen graph is an undirected graph with 10 vertices and 15 edges. It is a small graph that serves as a useful example and counterexample for many problems in graph theory. The Petersen graph is named after Julius Petersen, who in 1898 constructed it to be the smallest bridgeless cubic graph with no three-edge-coloring.

This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges.

In the mathematical field of graph theory, an edge-transitive graph is a graph G such that, given any two edges e1 and e2 of G, there is an automorphism of G that maps e1 to e2.

<span class="mw-page-title-main">Edge coloring</span> Problem of coloring a graphs edges such that meeting edges do not match

In graph theory, a proper edge coloring of a graph is an assignment of "colors" to the edges of the graph so that no two incident edges have the same color. For example, the figure to the right shows an edge coloring of a graph by the colors red, blue, and green. Edge colorings are one of several different types of graph coloring. The edge-coloring problem asks whether it is possible to color the edges of a given graph using at most k different colors, for a given value of k, or with the fewest possible colors. The minimum required number of colors for the edges of a given graph is called the chromatic index of the graph. For example, the edges of the graph in the illustration can be colored by three colors but cannot be colored by two colors, so the graph shown has chromatic index three.

<span class="mw-page-title-main">Cubic graph</span> Graph with all vertices of degree 3

In the mathematical field of graph theory, a cubic graph is a graph in which all vertices have degree three. In other words, a cubic graph is a 3-regular graph. Cubic graphs are also called trivalent graphs.

<span class="mw-page-title-main">Heawood graph</span> Undirected graph with 14 vertices

In the mathematical field of graph theory, the Heawood graph is an undirected graph with 14 vertices and 21 edges, named after Percy John Heawood.

<span class="mw-page-title-main">Symmetric graph</span> Graph in which all ordered pairs of linked nodes are automorphic

In the mathematical field of graph theory, a graph G is symmetric if, given any two pairs of adjacent vertices u1v1 and u2v2 of G, there is an automorphism

<span class="mw-page-title-main">Desargues graph</span> Distance-transitive cubic graph with 20 nodes and 30 edges

In the mathematical field of graph theory, the Desargues graph is a distance-transitive, cubic graph with 20 vertices and 30 edges. It is named after Girard Desargues, arises from several different combinatorial constructions, has a high level of symmetry, is the only known non-planar cubic partial cube, and has been applied in chemical databases.

<span class="mw-page-title-main">Gray graph</span>

In the mathematical field of graph theory, the Gray graph is an undirected bipartite graph with 54 vertices and 81 edges. It is a cubic graph: every vertex touches exactly three edges. It was discovered by Marion C. Gray in 1932 (unpublished), then discovered independently by Bouwer 1968 in reply to a question posed by Jon Folkman 1967. The Gray graph is interesting as the first known example of a cubic graph having the algebraic property of being edge but not vertex transitive.

<span class="mw-page-title-main">Kneser graph</span> Graph whose vertices correspond to combinations of a set of n elements

In graph theory, the Kneser graphK(n, k) (alternatively KGn,k) is the graph whose vertices correspond to the k-element subsets of a set of n elements, and where two vertices are adjacent if and only if the two corresponding sets are disjoint. Kneser graphs are named after Martin Kneser, who first investigated them in 1956.

<span class="mw-page-title-main">Coxeter graph</span> Cubic graph with 28 vertices and 42 edges

In the mathematical field of graph theory, the Coxeter graph is a 3-regular graph with 28 vertices and 42 edges. It is one of the 13 known cubic distance-regular graphs. It is named after Harold Scott MacDonald Coxeter.

<span class="mw-page-title-main">Hypercube graph</span> Graphs formed by a hypercubes edges and vertices

In graph theory, the hypercube graphQn is the graph formed from the vertices and edges of an n-dimensional hypercube. For instance, the cube graph Q3 is the graph formed by the 8 vertices and 12 edges of a three-dimensional cube. Qn has 2n vertices, 2n – 1n edges, and is a regular graph with n edges touching each vertex.

<span class="mw-page-title-main">Rook's graph</span> Graph of chess rook moves

In graph theory, a rook's graph is an undirected graph that represents all legal moves of the rook chess piece on a chessboard. Each vertex of a rook's graph represents a square on a chessboard, and there is an edge between any two squares sharing a row (rank) or column (file), the squares that a rook can move between. These graphs can be constructed for chessboards of any rectangular shape. Although rook's graphs have only minor significance in chess lore, they are more important in the abstract mathematics of graphs through their alternative constructions: rook's graphs are the Cartesian product of two complete graphs, and are the line graphs of complete bipartite graphs. The square rook's graphs constitute the two-dimensional Hamming graphs.

<span class="mw-page-title-main">Generalized Petersen graph</span> Family of cubic graphs formed from regular and star polygons

In graph theory, the generalized Petersen graphs are a family of cubic graphs formed by connecting the vertices of a regular polygon to the corresponding vertices of a star polygon. They include the Petersen graph and generalize one of the ways of constructing the Petersen graph. The generalized Petersen graph family was introduced in 1950 by H. S. M. Coxeter and was given its name in 1969 by Mark Watkins.

<span class="mw-page-title-main">Folkman graph</span> Bipartite 4-regular graph with 20 nodes and 40 edges

In the mathematical field of graph theory, the Folkman graph is a 4-regular graph with 20 vertices and 40 edges. It is a regular bipartite graph with symmetries taking every edge to every other edge, but the two sides of its bipartition are not symmetric with each other, making it the smallest possible semi-symmetric graph. It is named after Jon Folkman, who constructed it for this property in 1967.

<span class="mw-page-title-main">Hamiltonian decomposition</span>

In graph theory, a branch of mathematics, a Hamiltonian decomposition of a given graph is a partition of the edges of the graph into Hamiltonian cycles. Hamiltonian decompositions have been studied both for undirected graphs and for directed graphs. In the undirected case a Hamiltonian decomposition can also be described as a 2-factorization of the graph such that each factor is connected.

<span class="mw-page-title-main">Nauru graph</span> 24-vertex symmetric bipartite cubic graph

In the mathematical field of graph theory, the Nauru graph is a symmetric, bipartite, cubic graph with 24 vertices and 36 edges. It was named by David Eppstein after the twelve-pointed star in the flag of Nauru.

<span class="mw-page-title-main">Petersen's theorem</span>

In the mathematical discipline of graph theory, Petersen's theorem, named after Julius Petersen, is one of the earliest results in graph theory and can be stated as follows:

Petersen's Theorem. Every cubic, bridgeless graph contains a perfect matching.

In the mathematical field of graph theory, a prism graph is a graph that has one of the prisms as its skeleton.

<span class="mw-page-title-main">Locally linear graph</span> Graph where every edge is in one triangle

In graph theory, a locally linear graph is an undirected graph in which every edge belongs to exactly one triangle. Equivalently, for each vertex of the graph, its neighbors are each adjacent to exactly one other neighbor, so the neighbors can be paired up into an induced matching. Locally linear graphs have also been called locally matched graphs. Their triangles form the hyperedges of triangle-free 3-uniform linear hypergraphs and the blocks of certain partial Steiner triple systems, and the locally linear graphs are exactly the Gaifman graphs of these hypergraphs or partial Steiner systems.

References

  1. 1 2 Biggs, Norman L. (1976), "Automorphic graphs and the Krein condition", Geometriae Dedicata, 5 (1): 117–127, doi:10.1007/BF00148146 .
  2. 1 2 3 4 5 6 7 8 9 10 Biggs, Norman (1979), "Some odd graph theory", Second International Conference on Combinatorial Mathematics, Annals of the New York Academy of Sciences, 319: 71–81, doi:10.1111/j.1749-6632.1979.tb32775.x .
  3. West, Douglas B. (2000), "Exercise 1.1.28", Introduction to Graph Theory (2nd ed.), Englewood Cliffs, NJ: Prentice-Hall, p. 17.
  4. 1 2 Van Dam, Edwin; Haemers, Willem H. (2010), An Odd Characterization of the Generalized Odd Graphs, CentER Discussion Paper Series No. 2010-47, SSRN   1596575 .
  5. 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).
  6. Balaban, Alexandru T.; Fǎrcaşiu, D.; Bǎnicǎ, R. (1966), "Graphs of multiple 1, 2-shifts in carbonium ions and related systems", Rev. Roum. Chim., 11: 1205.
  7. Balaban, Alexandru T. (1972), "Chemical graphs, Part XIII: Combinatorial patterns", Rev. Roumaine Math. Pures Appl., 17: 3–16.
  8. Ghafoor, Arif; Bashkow, Theodore R. (1991), "A study of odd graphs as fault-tolerant interconnection networks", IEEE Transactions on Computers, 40 (2): 225–232, doi:10.1109/12.73594 .
  9. 1 2 Biggs, Norman (1972), Guy, Richard K. (ed.), "An edge-colouring problem", Research Problems, American Mathematical Monthly, 79 (9): 1018–1020, doi:10.2307/2318076, JSTOR   2318076 .
  10. Brouwer, Andries; Cohen, Arjeh M.; Neumaier, A. (1989), Distance-regular Graphs, ISBN   0-387-50619-5 .
  11. Ed Pegg, Jr. (December 29, 2003), Cubic Symmetric Graphs, Math Games, Mathematical Association of America, archived from the original on August 21, 2010, retrieved August 24, 2010.
  12. Babai, László (1995), "Automorphism groups, isomorphism, reconstruction", in Graham, Ronald L.; Grötschel, Martin; Lovász, László (eds.), Handbook of Combinatorics, vol. I, North-Holland, pp. 1447–1540, Proposition 1.9, archived from the original on June 11, 2010.
  13. Moon, Aeryung (1982), "Characterization of the odd graphs Ok by parameters", Discrete Mathematics, 42 (1): 91–97, doi: 10.1016/0012-365X(82)90057-7 .
  14. Godsil, C. D. (1980), "More odd graph theory", Discrete Mathematics, 32 (2): 205–207, doi: 10.1016/0012-365X(80)90055-2 .
  15. Watkins, Mark E. (1970), "Connectivity of transitive graphs", Journal of Combinatorial Theory , 8: 23–29, doi:10.1016/S0021-9800(70)80005-9, MR   0266804
  16. 1 2 3 Meredith, Guy H. J.; Lloyd, E. Keith (1973), "The footballers of Croam", Journal of Combinatorial Theory, Series B, 15 (2): 161–166, doi:10.1016/0095-8956(73)90016-6 .
  17. Mütze, Torsten; Nummenpalo, Jerri; Walczak, Bartosz (2018), "Sparse Kneser graphs are Hamiltonian", STOC'18—Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, New York: ACM, pp. 912–919, arXiv: 1711.01636 , MR   3826304