Count Petersen

Count Petersen
Count Petersen
Named after	Julius Petersen
Top	ten
Riber	15
Radius	2
Diameter	2
Girth	five
Automorphisms	120 (S 5 )
Chromatic number	3
Chromatic Index	four
Kind	one
The properties	Cubic; Very regular; Remote Transitive; Snark

The Petersen graph is an undirected graph with 10 vertices and 15 edges. This is a fairly simple graph, used as an example and counterexample for many problems in graph theory. The count is named after Julius Petersen , a Danish mathematician who built it in 1898 as the smallest cubic graph without bridges , without edge coloring in three colors. ^[one]

Although the count is usually attributed to Petersen, it was mentioned 12 years before its construction by Petersen in an article by Kempe ^[2] . Kempe noted that the vertices of this graph can be considered as ten lines of Desargues configuration , and its edges represent pairs of lines whose intersection does not belong to the configuration.

Donald Knuth argues that the Petersen graph is “a wonderful configuration giving counterexamples to many optimistic statements about which general statements can be true for graphs in general.” ^[3]

The Count of Petersen also appears in tropical geometry . The cone over the Petersen graph is naturally identified by the modular space of five-point rational tropical curves.

Build

Count Petersen as a Kneser count

KG_{5,2}

{\ displaystyle KG_ {5,2}}

KG _ {{5,2}}

The Petersen graph is an addition to the edge graph for $K_{5}$ ${\ displaystyle K_ {5}}$ $K_ {5}$ . The graph is also a Kneserian graph. $KG_{5,2}$ ${\ displaystyle KG_ {5,2}}$ $KG _ {{5,2}}$ . This means that the graph has one vertex for each 2-element subset of the 5-element set, and two vertices are connected by an edge if and only if the corresponding 2-element subsets do not intersect. As a Kneserian graph of the form $KG_{2n-1,n-1}$ ${\ displaystyle KG_ {2n-1, n-1}}$ the graph is an odd graph .

Geometrically, the Petersen graph is a graph formed by the vertices and edges of a half-dodecahedron , that is, a dodecahedron with identified opposite vertices, edges and faces.

Attachments

Count Petersen is not planar . Any non-planar graph has either a complete graph as minors $K_{5}$ ${\ displaystyle K_ {5}}$ or full bipartite graph $K_{3,3}$ ${\ displaystyle K_ {3,3}}$ but the Count of Petersen has both counts as minors. Minor $K_{5}$ ${\ displaystyle K_ {5}}$ can be obtained by tightening the edges of a perfect matching , for example, five short edges in the first figure. Minor $K_{3,3}$ ${\ displaystyle K_ {3,3}}$ can be obtained by dividing one vertex (for example, the central vertex of a 3-symmetric pattern) and contracting the edges incident to each neighbor of the remote vertex.

The Petersen graph has 2 intersections and is 1-planar .

The generally accepted most symmetrical flat design of the Petersen graph in the form of a pentagon inside a pentagon has five intersections. However, this is not the most optimal figure that minimizes the number of intersections. There is another figure (shown on the right) with only two intersections. Thus, the Petersen graph has the number of intersections 2. Each edge in this figure intersects no more than once, so the Petersen graph is 1-planar . On the torus, the Petersen graph can be drawn without crossing the edges. Thus, the graph has orientable genus 1.

The Petersen graph is a graph of unit distances — it can be drawn on a plane with edges of unit length.

The Petersen graph can also be drawn (with intersections) on a plane so that all edges have the same length. Thus, the graph is a graph of unit distances .

The simplest into which the Petersen graph can be embedded without intersections is the projective plane . This is the embedding given by the construction of the Petersen graph as a half-dodecahedron . An attachment to the projective plane can also be formed from a standard pentagonal figure of Count Petersen by placing a (a cut Klein bottle) inside a pentagonal star in the center of the picture and directing the edges of the star through this film. The resulting pattern has six pentagonal faces. This construction forms a and shows that the Petersen graph has a nonorientable genus 1.

Symmetries

The Petersen graph is strongly regular (with signature srg (10,3,0,1)). The graph is also symmetric , which means that it is edge-transitive and vertex-transitive . More strictly, the graph is 3-transitive in arcs - any oriented path of three paths in the Petersen graph can be translated into any other such path by the symmetry of the graph ^[4] . A graph is one of 13 cubic distance-regular graphs . ^[five]

The group of automorphisms of the Petersen graph is a symmetric group $S_{5}$ ${\ displaystyle S_ {5}}$ . Act $S_{5}$ ${\ displaystyle S_ {5}}$ on the Petersen graph follows from its construction in the form of a Kneser graph . Any homeomorphism of the Petersen graph onto itself that does not identify adjacent vertices is an automorphism. As shown in the illustrations, the drawings of the Petersen graph can show symmetries in five directions or in three directions, but it is impossible to draw the Petersen graph on a plane so that the figure shows the full symmetry of the group of the graph.

Despite its high symmetry, the Petersen graph is not a Cayley graph ; it is the smallest vertex-transitive graph that is not a Cayley graph. ^[6]

Hamiltonian paths and cycles

The Petersen graph is hypogamiltonian - removing any vertex, such as the central vertex in the figure, makes the graph Hamiltonian. A drawing with three symmetries was proposed by Kempe ( Kempe 1886 ).

The Petersen graph has a Hamiltonian path , but not a Hamiltonian cycle . A graph is the smallest cubic graph without a bridge that does not have a Hamiltonian cycle. The graph is hypogamiltonian , which means that although it does not have a Hamiltonian cycle, deleting any vertex makes it Hamiltonian, and this is the smallest hypogamiltonian graph.

As a finite connected vertex-transitive graph that does not have a Hamiltonian cycle, the Petersen graph is a counterexample of a variant of the Lovas conjecture , but the canonical formulation of the hypothesis asks about the Hamiltonian path and this hypothesis holds for the Petersen graph.

Only five connected vertex-transitive graphs without Hamiltonian cycles are known - the complete graph K ₂ , the Petersen graph, the Coxeter graph and two graphs obtained from the Petersen and Coxeter graphs by replacing each vertex with a triangle ^[7] . If G is a 2-connected, r- regular graph with a maximum of 3 r + 1 vertices, then G is Hamiltonian or G is a Petersen graph ^[8] .

To show that the Petersen graph does not have a Hamiltonian cycle C , we consider the edges connecting the inner cycle of 5 vertices with the outer cycle. If there is a Hamiltonian cycle, an even number of these edges must be chosen. If only two edges are selected, their final vertices must be adjacent in one of the cycles with 5 vertices, which is impossible. Thus, 4 ribs must be selected. Suppose that the top edge is not selected (all other cases are similar due to symmetry). Of the 5 edges of the outer cycle, the two upper edges must be included in the Hamiltonian cycle, so that two side edges should not be included in the cycle, and then the lower edge should be included in the cycle. The two upper edges in the inner cycle must be selected, but then these two edges close the cycle, which is not complete, so that it cannot be part of the Hamiltonian cycle. Alternatively, we can consider 3-regular graphs with ten vertices that have a Hamiltonian cycle and show that none of these graphs is a Petersen graph by finding a cycle in each of them that is shorter than any cycle of the Petersen graph. Any Hamiltonian 3-regular graph with ten vertices consists of a cycle with ten vertices of cycle C , plus five chords. If any chord connects two vertices along C at a distance of two or three from each other, then the graph has a 3-cycle or 4-cycle, and therefore cannot be a Petersen graph. If two chords connect the opposite vertices of cycle C at a distance of four along C , there is again a 4-cycle. All that remains is the case of the Mobius staircase , formed by connecting each pair of opposite sides with a chord, which again has a 4-cycle. Since the circumference of Count Petersen is five, it cannot be formed in this way, and therefore does not have a Hamiltonian cycle.

Coloring

Count Petersen's Ribs in 4 Colors

Coloring the vertices of Count Petersen in 3 colors

The Petersen graph has a chromatic number of 3, which means that the vertices of the graph can be painted in three colors, but not in two, so that no edge connects two vertices of the same color. The graph has a prescribed coloring in 3 colors according to the Brooks theorem for prescribed coloring. The Petersen graph has a chromatic index of 4, that is, the coloring of the edges requires four colors. In other words, the graph is not the sum of three 1-factors , which was shown by Petersen himself ^[9] . To prove this, it is necessary to check four cases to show that there is no coloring of edges in 3 colors. Like a connected cubic graph without bridges with a chromatic index of four, the Petersen graph is a snark . This graph is the smallest snark possible. He was the only known snark from 1898 to 1946. The snark theorem, formulated by the Tatt hypothesis (its proof was announced in 2001 by Robertson, Sanders, Seymour and Thomas ^[10] ), states that any snark has a graph Petersen as a minor .

In addition, the graph has a fractional chromatic index of 3, which confirms the statement that the difference between the chromatic index and fractional chromatic index can be 1. The old Goldberg – Seymour hypothesis suggests that this is the largest possible difference.

The Thue number (variant of the chromatic index) of the Petersen graph is 5.

The Petersen Count requires at least three colors in any (possibly improper) coloring that violates all symmetries. That is, the graph is three. With the exception of complete graphs, there is only a Kneser graph whose characteristic number is not equal to two ^[11] .

Other properties

Count Petersen:

is 3-connected, and therefore cost-effective 3-connected and without bridges. See Connected Graph .
has an independence number of 4 and is 3-partite. See the Problem on an Independent Set .
is a cubic graph , has a dominance number of 3, has perfect matching and a 2-factor .
has 6 different perfect matchings.
is the smallest cubic graph with a girth of 5. (This is the only $(3,5)$ ${\ displaystyle (3,5)}$ - cell . The graph has only 10 vertices, so it is the only one $(3,5)$ ${\ displaystyle (3,5)}$ - Earl of Moore .) ^[12] .
has a radius of 2 and a diameter of 2. This is the largest cubic graph with a diameter of 2 ^[13]
has a spectrum of the graph −2, −2, −2, −2, 1, 1, 1, 1, 1, 1, 3.
has 2000 spanning trees , more than any 10-vertex cubic graph ^[14]
has a chromatic polynomial $t(t-1)(t-2)\left(t^{7}-12t^{6}+67t^{5}-230t^{4}+529t^{3}-814t^{2}+775t-352\right).$ ${\ displaystyle t (t-1) (t-2) \ left (t ^ {7} -12t ^ {6} + 67t ^ {5} -230t ^ {4} + 529t ^ {3} -814t ^ { 2} + 775t-352 \ right).}$ ^[15]
has a characteristic polynomial $(t-1)^{5}(t+2)^{4}(t-3)$ ${\ displaystyle (t-1) ^ {5} (t + 2) ^ {4} (t-3)}$ , which makes it a whole graph - a graph whose spectrum consists entirely of integers.
Between any two peaks there is a single path of length no more than two.

Petersenov family of graphs .

Petersen Hypothesis on Coloring

According to Devos, Neshetril and Raspo, “ The cycle of graph G is the set C $\subseteq$ ${\ displaystyle \ subseteq}$ E (G), such that any vertex of the graph (V (G), C) has an even degree. If G, H are graphs, we define a map φ: E (G) -> E (H) to be continuous in cycles , if the inverse image of any cycle in H is a cycle in G. François Jaeger formulated a conjecture that states that any graph without bridges has a cycle-continuous mapping into a Petersen graph. Gager showed that if the hypothesis is true, then the hypothesis of double covering by cycles of length 5 and the Berge – Fulkerson conjecture are also true. ” ^[16] .

Related Graphs

The generalized Petersen graph G ( n , k ) is formed by connecting the vertices of a regular n- gon with the corresponding vertices of a star-shaped polygon with the Schlefley symbol { n / k } ^[17] ^[18] . For example, in these notations, the Petersen graph is designated G (5,2) - it can be formed by connecting the corresponding vertices of a pentagon and a pentagonal star, while the vertices of the star are connected through one. The generalized Petersen graphs also include n- prisms G ( n , 1), the Dürer graph G (6,2), the Mobius – Cantor graph G (8,3), the dodecahedron graph G (10,2), the Desargues graph G (10, 3) and the graph of Nauru G (12.5).

The Petersen family of graphs consists of seven graphs that can be formed from the Petersen graph by zero or more applications of Δ-Y or Y-Δ transformations . The complete graph K _{6 is} also a member of the Petersen family. These graphs form forbidden minors for graphs that can be embedded without links , graphs that can be embedded in three-dimensional space in such a way that no two cycles in the graph are linked ^[19]

The Clebsch graph consists of copies of the Petersen graph as generated subgraphs - for each vertex v of the Clebsch graph, ten non-neighbors of vertices v generate a copy of the Petersen graph.

Notes

↑ The Petersen graph .
↑ Kempe, 1886 .
↑ Knuth, 2011 .
↑ Babai, 1995 , p. 1447-1540.
↑ According to the Foster List .
↑ As indicated, this assumes that Cayley graphs are not necessarily connected. Some sources require Cayley graphs to be connected, which makes two-vertex graph the smallest vertex-transitive graph that is not a Cayley graph. By the definition given in these sources, the Petersen graph is the smallest connected vertex-transitive graph that is not a Cayley graph.
↑ Royle, G. “Cubic Symmetric Graphs (The Foster Census).” Archived July 20, 2008.
↑ Holton, Sheehan, 1993 , p. 32.
↑ Harari, 2003 , p. 113.
↑ Pegg, 2002 , p. 1084-1086.
↑ Albertson, Boutin, 2007 , p. R20.
↑ Hoffman, Singleton, 1960 , p. 497-504.
↑ This follows from the fact that the graph is a Moore graph, since the Moore graph is the largest possible regular graph with such a degree of vertices and diameter ( Hoffman, Singleton 1960 ).
↑ Jakobson, Rivin, 1999 ; Valdes, 1991 . Cubic graphs with 6 and 8 vertices, on which the number of spanning trees is maximized, are Mobius stairs .
↑ Biggs, 1993 .
↑ DeVos, Nešetřil, Raspaud, 2007 , p. 109-138.
↑ Coxeter 1950 .
↑ Watkins, 1969 .
↑ Bailey, 1997 , p. 187.

Literature

F. Harari. Graph theory. - M .: URSS , 2003. - ISBN 5-354-00301-6 .
O. Auray . Graph theory. - M .: URSS , 2008 .-- ISBN 978-5-397-00044-4 .
Ed Pegg, Jr. Book Review: The Colossal Book of Mathematics // Notices of the American Mathematical Society. - 2002. - T. 49 , no. 9 . - DOI : 10.1109 / TED.2002.1003756 . - .
Rosemary A. Bailey. Surveys in Combinatorics. - Cambridge University Press, 1997. - ISBN 978-0-521-59840-8 .
Matt DeVos, Jaroslav Nešetřil, André Raspaud. On edge-maps whose inverse preserves flows or tensions // Graph theory in Paris. - Basel: Birkhäuser, 2007 .-- pp. 109–138. - (Trends Math.). - DOI : 10.1007 / 978-3-7643-7400-6_10 .
Norman Biggs. Algebraic Graph Theory. - 2nd. - Cambridge: Cambridge University Press, 1993 .-- ISBN 0-521-45897-8 .
László Babai. Automorphism groups, isomorphism, reconstruction // Handbook of Combinatorics / Ronald L. Graham, Martin Grötschel, László Lovász. - North-Holland, 1995. - T. I. Archived June 11, 2010. Archived June 11, 2010 on the Wayback Machine
Alan J. Hoffman, Robert R. Singleton. Moore graphs with diameter 2 and 3 // IBM Journal of Research and Development. - 1960.- T. 5 , no. 4 . - S. 497-504 . - DOI : 10.1147 / rd . 45.0497 .
Michael O. Albertson, Debra L. Boutin. Using determining sets to distinguish Kneser graphs // Electronic Journal of Combinatorics. - 2007.- T. 14 , no. 1 .
Geoffrey Exoo, Frank Harary, Frank Harary. The crossing numbers of some generalized Petersen graphs // Mathematica Scandinavica. - 1981. - T. 48 . - S. 184–188 .
HSM Coxeter. Self-dual configurations and regular graphs // Bulletin of the American Mathematical Society . - 1950 .-- T. 56 , no. 5 . - S. 413–455 . - DOI : 10.1090 / S0002-9904-1950-09407-5 .
DA Holton, J. Sheehan. The Petersen Graph . - Cambridge University Press , 1993. - ISBN 0-521-43594-3 . - DOI : 10.2277 / 0521435943 . Archived February 8, 2008 on Wayback Machine
Dmitry Jakobson, Igor Rivin. On some extremal problems in graph theory. - 1999 .-- arXiv : math.CO/9907050 .
AB Kempe. A memoir on the theory of mathematical form // Philosophical Transactions of the Royal Society of London. - 1886. - T. 177 . - S. 1–70 . - DOI : 10.1098 / rstl . 1886.0002 .
László Lovász . Combinatorial Problems and Exercises. - 2nd. - North-Holland, 1993. - ISBN 0-444-81504-X .
Julius Petersen. Sur le théorème de Tait // L'Intermédiaire des Mathématiciens. - 1898.- T. 5 . - S. 225–227 .
AJ Schwenk. Enumeration of Hamiltonian cycles in certain generalized Petersen graphs // Journal of Combinatorial Theory . - 1989.- T. 47 , no. 1 . - S. 53–59 . - DOI : 10.1016 / 0095-8956 (89) 90064-6 .
L. Valdes. Extremal properties of spanning trees in cubic graphs // Congressus Numerantium. - 1991 .-- T. 85 . - S. 143–160 .
Mark E. Watkins. A Theorem on Tait Colorings with an Application to the Generalized Petersen Graphs // Journal of Combinatorial Theory . - 1969. - T. 6 , no. 2 . - S. 152–164 . - DOI : 10.1016 / S0021-9800 (69) 80116-X .
Donald E. Knuth . A draft of section 7: Introduction to combinatorial searching // The Art of Computer Programming . - T. 4, pre-fascicle 0A.
- Donald E. Knuth . Combinatorial Algorithms, Part 1. - Upper Saddle River, New Jersey: Addison-Wesley, 2011 .-- ISBN 0-201-03804-8 .
- Donald E. Knut . Chapter 7: Combinatorial Search // The Art of Programming. - Moscow, St. Petersburg, Kiev: LLC “I.D. Williams ”, 2013. - V. 4, A / Combinatorial algorithms, part 1. - ISBN 978-5-8459-1744-7 LBC 32.973.26-18.2.75.

Links

Keller, Mitch. Kneser graphs PlanetMath
Weisstein, Eric W. Petersen Graph on Wolfram MathWorld .
Petersen Graph in the Encyclopedia of Integer Sequences

[1] The Petersen graph .

[_be621b903a8e09ae-2] Kempe, 1886 .

[_2e2cd18d3a275a1f-3] Knuth, 2011 .

[_d66a805468691aff-4] Babai, 1995 , p. 1447-1540.

[5] According to the Foster List .

[6] As indicated, this assumes that Cayley graphs are not necessarily connected. Some sources require Cayley graphs to be connected, which makes two-vertex graph the smallest vertex-transitive graph that is not a Cayley graph. By the definition given in these sources, the Petersen graph is the smallest connected vertex-transitive graph that is not a Cayley graph.

[7] Royle, G. “Cubic Symmetric Graphs (The Foster Census).” Archived July 20, 2008.

[_cce47418f8970dee-8] Holton, Sheehan, 1993 , p. 32.

[_32f947f53d36cf40-9] Harari, 2003 , p. 113.

[_15ad318d23fc5f99-10] Pegg, 2002 , p. 1084-1086.

[_5aa5cf8cef184773-11] Albertson, Boutin, 2007 , p. R20.

[_04cdf7a143bc22b5-12] Hoffman, Singleton, 1960 , p. 497-504.

[13] This follows from the fact that the graph is a Moore graph, since the Moore graph is the largest possible regular graph with such a degree of vertices and diameter ( Hoffman, Singleton 1960 ).

[14] Jakobson, Rivin, 1999 ; Valdes, 1991 . Cubic graphs with 6 and 8 vertices, on which the number of spanning trees is maximized, are Mobius stairs .

[_65b1d35ad8c911c9-15] Biggs, 1993 .

[_97599479c5543277-16] DeVos, Nešetřil, Raspaud, 2007 , p. 109-138.

[_6c81e292c11f6f76-17] Coxeter 1950 .

[_9d7f3e9920de123d-18] Watkins, 1969 .

[_d42fe49ddf87ca7d-19] Bailey, 1997 , p. 187.