definition of Wikipedia
Advertizing ▼
Petersen graph  

The Petersen graph is most commonly drawn as a pentagon with a pentagram inside, with five spokes. 

Named after  Julius Petersen 
Vertices  10 
Edges  15 
Radius  2 
Diameter  2 
Girth  5 
Automorphisms  120 (S_{5}) 
Chromatic number  3 
Chromatic index  4 
Fractional chromatic index  3 
Properties  Cubic Strongly regular Distancetransitive Snark 
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 for Julius Petersen, who in 1898 constructed it to be the smallest bridgeless cubic graph with no threeedgecoloring.^{[1]} Although the graph is generally credited to Petersen, it had in fact first appeared 12 years earlier, in a paper by A. B. Kempe (1886).
Donald Knuth states that the Petersen graph is "a remarkable configuration that serves as a counterexample to many optimistic predictions about what might be true for graphs in general."^{[2]}
Contents 
The Petersen graph is the complement of the line graph of . It is also the Kneser graph ; this means that it has one vertex for each 2element subset of a 5element set, and two vertices are connected by an edge if and only if the corresponding 2element subsets are disjoint from each other. As a Kneser graph of the form it is an example of an odd graph.
Geometrically, the Petersen graph is the graph formed by the vertices and edges of the hemidodecahedron, that is, a dodecahedron with opposite points, lines and faces identified together.
The Petersen graph is nonplanar. Any nonplanar graph has as minors either the complete graph , or the complete bipartite graph , but the Petersen graph has both as minors. The minor can be formed by contracting the edges of a perfect matching, for instance the five short edges in the first picture. The minor can be formed by deleting one vertex (for instance the central vertex of the 3symmetric drawing) and contracting an edge incident to each neighbor of the deleted vertex.
The most common and symmetric plane drawing of the Petersen graph, as a pentagram within a pentagon, has five crossings. However, this is not the best drawing for minimizing crossings; there exists another drawing (shown in the figure) with only two crossings. Thus, the Petersen graph has crossing number 2. On a torus the Petersen graph can be drawn without edge crossings; it therefore has orientable genus 1.
The Petersen graph can also be drawn (with crossings) in the plane in such a way that all the edges have equal length. That is, it is a unit distance graph.
The simplest nonorientable surface on which the Petersen graph can be embedded without crossings is the projective plane. This is the embedding given by the hemidodecahedron construction of the Petersen graph. The projective plane embedding can also be formed from the standard pentagonal drawing of the Petersen graph by placing a crosscap within the fivepoint star at the center of the drawing, and routing the star edges through this crosscap; the resulting drawing has six pentagonal faces. This construction forms a regular map and shows that the Petersen graph has nonorientable genus 1.
The Petersen graph is strongly regular (with signature srg(10,3,0,1)). It is also symmetric, meaning that it is edge transitive and vertex transitive. More strongly, it is 3arctransitive: every directed threeedge path in the Petersen graph can be transformed into every other such path by a symmetry of the graph.^{[3]} It is one of only 13 cubic distanceregular graphs.^{[4]}
The automorphism group of the Petersen graph is the symmetric group ; the action of on the Petersen graph follows from its construction as a Kneser graph. Every homomorphism of the Petersen graph to itself that doesn't identify adjacent vertices is an automorphism. As shown in the figures, the drawings of the Petersen graph may exhibit fiveway or threeway symmetry, but it is not possible to draw the Petersen graph in the plane in such a way that the drawing exhibits the full symmetry group of the graph.
Despite its high degree of symmetry, the Petersen graph is not a Cayley graph. It is the smallest vertextransitive graph that is not a Cayley graph.^{[5]}
The Petersen graph has a Hamiltonian path but no Hamiltonian cycle. It is the smallest bridgeless cubic graph with no Hamiltonian cycle. It is hypohamiltonian, meaning that although it has no Hamiltonian cycle, deleting any vertex makes it Hamiltonian, and is the smallest hypohamiltonian graph.
As a finite connected vertextransitive graph that does not have a Hamiltonian cycle, the Petersen graph is a counterexample to a variant of the Lovász conjecture, but the canonical formulation of the conjecture asks for a Hamiltonian path and is verified by the Petersen graph.
Only five vertextransitive graphs with no Hamiltonian cycles are known: the complete graph K_{2}, the Petersen graph, the Coxeter graph and two graphs derived from the Petersen and Coxeter graphs by replacing each vertex with a triangle.^{[6]} If G is a 2connected, rregular graph with at most 3r + 1 vertices, then G is Hamiltonian or G is the Petersen graph.^{[7]}
To see that the Petersen graph has no Hamiltonian cycle C, we describe the tenvertex 3regular graphs that do have a Hamiltonian cycle and show that none of them is the Petersen graph, by finding a cycle in each of them that is shorter than any cycle in the Petersen graph. Any tenvertex Hamiltonian 3regular graph consists of a tenvertex cycle C plus five chords. If any chord connects two vertices at distance two or three along C from each other, the graph has a 3cycle or 4cycle, and therefore cannot be the Petersen graph. If two chords connect opposite vertices of C to vertices at distance four along C, there is again a 4cycle. The only remaining case is a Möbius ladder formed by connecting each pair of opposite vertices by a chord, which again has a 4cycle. Since the Petersen graph has girth five, it cannot be formed in this way and has no Hamiltonian cycle.
The Petersen graph has chromatic number 3, meaning that its vertices can be colored with three colors — but not with two — such that no edge connects vertices of the same color.
The Petersen graph has chromatic index 4; coloring the edges requires four colors. A proof of this requires checking four cases to demonstrate that no 3edgecoloring exists. As a connected bridgeless cubic graph with chromatic index four, the Petersen graph is a snark. It is the smallest possible snark, and was the only known snark from 1898 until 1946. The snark theorem, a result conjectured by W. T. Tutte and announced in 2001 by Robertson, Sanders, Seymour, and Thomas,^{[8]} states that every snark has the Petersen graph as a minor.
Additionally, the graph has fractional chromatic index 3, proving that the difference between the chromatic index and fractional chromatic index can be as large as 1. The longstanding GoldbergSeymour Conjecture proposes that this is the largest gap possible.
The Thue number (a variant of the chromatic index) of the Petersen graph is 5.
The Petersen graph:
According to DeVos, Nesetril, and Raspaul, "A cycle of a graph G is a set C E(G) so that every vertex of the graph (V(G),C) has even degree. If G,H are graphs, we define a map φ: E(G) —> E(H) to be cyclecontinous if the preimage of every cycle of H is a cycle of G. A fascinating onjecture of Jaeger asserts that every bridgeless graph has a cyclecontinous mapping to the Petersen graph. Jaeger showed that if this conjecture is true, then so is the 5cycledoublecover conjecture and the BergeFulkerson conjecture."^{[13]}
The generalized Petersen graph G(n,k) is formed by connecting the vertices of a regular ngon to the corresponding vertices of a star polygon with Schläfli symbol {n/k}.^{[14]} For instance, in this notation, the Petersen graph is G(5,2): it can be formed by connecting corresponding vertices of a pentagon and fivepoint star, and the edges in the star connect every second vertex. The generalized Petersen graphs also include the nprism G(n,1) the Dürer graph G(6,2), the MöbiusKantor graph G(8,3), the dodecahedron G(10,2), the Desargues graph G(10,3) and the Nauru graph G(12,5).
The Petersen family consists of the seven graphs that can be formed from the Petersen graph by zero or more applications of ΔY or YΔ transforms. The complete graph K_{6} is also in the Petersen family. These graphs form the forbidden minors for linklessly embeddable graphs, graphs that can be embedded into threedimensional space in such a way that no two cycles in the graph are linked.^{[15]}
The Clebsch graph contains many copies of the Petersen graph as induced subgraphs: for each vertex v of the Clebsch graph, the ten nonneighbors of v induce a copy of the Petersen graph.
Wikimedia Commons has media related to: Petersen graph 
sensagent's content
Dictionary and translator for handheld
New : sensagent is now available on your handheld
Advertising ▼
Webmaster Solution
Alexandria
A windows (popinto) of information (fullcontent of Sensagent) triggered by doubleclicking any word on your webpage. Give contextual explanation and translation from your sites !
SensagentBox
With a SensagentBox, visitors to your site can access reliable information on over 5 million pages provided by Sensagent.com. Choose the design that fits your site.
Business solution
Improve your site content
Add new content to your site from Sensagent by XML.
Crawl products or adds
Get XML access to reach the best products.
Index images and define metadata
Get XML access to fix the meaning of your metadata.
Please, email us to describe your idea.
Lettris
Lettris is a curious tetrisclone game where all the bricks have the same square shape but different content. Each square carries a letter. To make squares disappear and save space for other squares you have to assemble English words (left, right, up, down) from the falling squares.
boggle
Boggle gives you 3 minutes to find as many words (3 letters or more) as you can in a grid of 16 letters. You can also try the grid of 16 letters. Letters must be adjacent and longer words score better. See if you can get into the grid Hall of Fame !
English dictionary
Main references
Most English definitions are provided by WordNet .
English thesaurus is mainly derived from The Integral Dictionary (TID).
English Encyclopedia is licensed by Wikipedia (GNU).
Copyrights
The wordgames anagrams, crossword, Lettris and Boggle are provided by Memodata.
The web service Alexandria is granted from Memodata for the Ebay search.
The SensagentBox are offered by sensAgent.
Translation
Change the target language to find translations.
Tips: browse the semantic fields (see From ideas to words) in two languages to learn more.
last searches on the dictionary :
computed in 0.125s