 | |
| Author |
|
|---|---|
| Series | Australian Mathematical Society Lecture Series |
| Subject | The Petersen graph |
| Publisher | Cambridge University Press |
Publication date | 1993 |
The Petersen Graph is a mathematics book about the Petersen graph and its applications in graph theory. It was written by Derek Holton and John Sheehan, and published in 1993 by the Cambridge University Press as volume 7 in their Australian Mathematical Society Lecture Series.
The Petersen graph is an undirected graph with ten vertices and fifteen edges, commonly drawn as a pentagram within a pentagon, with corresponding vertices attached to each other. It has many unusual mathematical properties, and has frequently been used as a counterexample to conjectures in graph theory. [1] [2] The book uses these properties as an excuse to cover several advanced topics in graph theory where this graph plays an important role. [1] [3] It is heavily illustrated, and includes both open problems on the topics it discusses and detailed references to the literature on these problems. [1] [4]
After an introductory chapter, the second and third chapters concern graph coloring, the history of the four color theorem for planar graphs, its equivalence to 3-edge-coloring of planar cubic graphs, the snarks (cubic graphs that have no such colorings), and the conjecture of W. T. Tutte that every snark has the Petersen graph as a graph minor. Two more chapters concern closely related topics, perfect matchings (the sets of edges that can have a single color in a 3-edge-coloring) and nowhere-zero flows (the dual concept to planar graph coloring). The Petersen graph shows up again in another conjecture of Tutte, that when a bridgeless graph does not have the Petersen graph as a minor, it must have a nowhere-zero 4-flow. [3]
Chapter six of the book concerns cages, the smallest regular graphs with no cycles shorter than a given length. The Petersen graph is an example: it is the smallest 3-regular graph with no cycles of length shorter than 5. Chapter seven is on hypohamiltonian graphs, the graphs that do not have a Hamiltonian cycle through all vertices but that do have cycles through every set of all but one vertices; the Petersen graph is the smallest example. The next chapter concerns the symmetries of graphs, and types of graphs defined by their symmetries, including the distance-transitive graphs and strongly regular graphs (of which the Petersen graph is an example) [3] and the Cayley graphs (of which it is not). [1] The book concludes with a final chapter of miscellaneous topics too small for their own chapters. [3]
The book assumes that its readers already have some familiarity with graph theory. [3] It can be used as a reference work for researchers in this area, [1] [2] or as the basis of an advanced course in graph theory. [2] [3]
Although Carsten Thomassen describes the book as "elegant", [4] and Robin Wilson evaluates its exposition as "generally good", [2] reviewer Charles H. C. Little takes the opposite view, finding fault with its copyediting, with some of its mathematical notation, and with its failure to discuss the lattice of integer combinations of perfect matchings, in which the number of copies of the Petersen graph in the "bricks" of a certain graph decomposition plays a key role in computing the dimension. [1] Reviewer Ian Anderson notes the superficiality of some of its coverage, but concludes that the book "succeeds in giving an exciting and enthusiastic glimpse" of graph theory. [3]
In graph theory, the girth of an undirected graph is the length of a shortest cycle contained in the graph. If the graph does not contain any cycles, its girth is defined to be infinity. For example, a 4-cycle (square) has girth 4. A grid has girth 4 as well, and a triangular mesh has girth 3. A graph with girth four or more is triangle-free.
In mathematics, Tait's conjecture states that "Every 3-connected planar cubic graph has a Hamiltonian cycle through all its vertices". It was proposed by P. G. Tait and disproved by W. T. Tutte, who constructed a counterexample with 25 faces, 69 edges and 46 vertices. Several smaller counterexamples, with 21 faces, 57 edges and 38 vertices, were later proved minimal by Holton & McKay (1988). The condition that the graph be 3-regular is necessary due to polyhedra such as the rhombic dodecahedron, which forms a bipartite graph with six degree-four vertices on one side and eight degree-three vertices on the other side; because any Hamiltonian cycle would have to alternate between the two sides of the bipartition, but they have unequal numbers of vertices, the rhombic dodecahedron is not Hamiltonian.
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.
In graph theory, a uniquely colorable graph is a k-chromatic graph that has only one possible (proper) k-coloring up to permutation of the colors. Equivalently, there is only one way to partition its vertices into k independent sets and there is no way to partition them into k − 1 independent sets.
In the mathematical field of graph theory, a snark is an undirected graph with exactly three edges per vertex whose edges cannot be colored with only three colors. In order to avoid trivial cases, snarks are often restricted to have additional requirements on their connectivity and on the length of their cycles. Infinitely many snarks exist.
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.
In graph theory, the Hadwiger conjecture states that if is loopless and has no minor then its chromatic number satisfies . It is known to be true for . The conjecture is a generalization of the four-color theorem and is considered to be one of the most important and challenging open problems in the field.
In graph theory, a nowhere-zero flow or NZ flow is a network flow that is nowhere zero. It is intimately connected to coloring planar graphs.
In the mathematical field of graph theory, a graph G is said to be hypohamiltonian if G itself does not have a Hamiltonian cycle but every graph formed by removing a single vertex from G is Hamiltonian.
In the mathematical field of graph theory, Tietze's graph is an undirected cubic graph with 12 vertices and 18 edges. It is named after Heinrich Franz Friedrich Tietze, who showed in 1910 that the Möbius strip can be subdivided into six regions that all touch each other – three along the boundary of the strip and three along its center line – and therefore that graphs that are embedded onto the Möbius strip may require six colors. The boundary segments of the regions of Tietze's subdivision form an embedding of Tietze's graph.
In graph-theoretic mathematics, a cycle double cover is a collection of cycles in an undirected graph that together include each edge of the graph exactly twice. For instance, for any polyhedral graph, the faces of a convex polyhedron that represents the graph provide a double cover of the graph: each edge belongs to exactly two faces.
In graph theory, Grinberg's theorem is a necessary condition for a planar graph to contain a Hamiltonian cycle, based on the lengths of its face cycles. If a graph does not meet this condition, it is not Hamiltonian. The result has been widely used to prove that certain planar graphs constructed to have additional properties are not Hamiltonian; for instance it can prove non-Hamiltonicity of some counterexamples to Tait's conjecture that cubic polyhedral graphs are Hamiltonian.
In the mathematical field of graph theory, the flower snarks form an infinite family of snarks introduced by Rufus Isaacs in 1975.
In the mathematical field of graph theory, the Tutte graph is a 3-regular graph with 46 vertices and 69 edges named after W. T. Tutte. It has chromatic number 3, chromatic index 3, girth 4 and diameter 8.
In geometric graph theory, a branch of mathematics, a polyhedral graph is the undirected graph formed from the vertices and edges of a convex polyhedron. Alternatively, in purely graph-theoretic terms, the polyhedral graphs are the 3-vertex-connected, planar graphs.
In graph theory, a branch of mathematics, the Herschel graph is a bipartite undirected graph with 11 vertices and 18 edges. It is a polyhedral graph, and is the smallest polyhedral graph that does not have a Hamiltonian cycle, a cycle passing through all its vertices. It is named after British astronomer Alexander Stewart Herschel, because of Herschel's studies of Hamiltonian cycles in polyhedral graphs.
Barnette's conjecture is an unsolved problem in graph theory, a branch of mathematics, concerning Hamiltonian cycles in graphs. It is named after David W. Barnette, a professor emeritus at the University of California, Davis; it states that every bipartite polyhedral graph with three edges per vertex has a Hamiltonian cycle.
In the mathematical field of graph theory, a zero-symmetric graph is a connected graph in which each vertex has exactly three incident edges and, for each two vertices, there is a unique symmetry taking one vertex to the other. Such a graph is a vertex-transitive graph but cannot be an edge-transitive graph: the number of symmetries equals the number of vertices, too few to take every edge to every other edge.
The Wiener–Araya graph is, in graph theory, a graph on 42 vertices with 67 edges. It is hypohamiltonian, which means that it does not itself have a Hamiltonian cycle but every graph formed by removing a single vertex from it is Hamiltonian. It is also planar.