About: Pancake graph

An Entity of Type: Thing, from Named Graph: http://dbpedia.org, within Data Space: dbpedia.org

In the mathematical field of graph theory, the pancake graph Pn or n-pancake graph is a graph whose vertices are the permutations of n symbols from 1 to n and its edges are given between permutations transitive by prefix reversals. The pancake graph of dimension n, Pn, is a regular graph with vertices. Its degree is n − 1, hence, according to the handshaking lemma, it has edges. Pn can be constructed recursively from n copies of Pn−1, by assigning a different element from the set {1, 2, …, n} as a suffix to each copy.

thumbnail
Property Value
dbo:abstract
  • In the mathematical field of graph theory, the pancake graph Pn or n-pancake graph is a graph whose vertices are the permutations of n symbols from 1 to n and its edges are given between permutations transitive by prefix reversals. Pancake sorting is the colloquial term for the mathematical problem of sorting a disordered stack of pancakes in order of size when a spatula can be inserted at any point in the stack and used to flip all pancakes above it. A pancake number is the minimum number of flips required for a given number of pancakes. Obtaining the pancake number is equivalent to the problem of obtaining the diameter of the pancake graph. The pancake graph of dimension n, Pn, is a regular graph with vertices. Its degree is n − 1, hence, according to the handshaking lemma, it has edges. Pn can be constructed recursively from n copies of Pn−1, by assigning a different element from the set {1, 2, …, n} as a suffix to each copy. (en)
dbo:thumbnail
dbo:wikiPageID
  • 54755877 (xsd:integer)
dbo:wikiPageLength
  • 16573 (xsd:nonNegativeInteger)
dbo:wikiPageRevisionID
  • 1095047927 (xsd:integer)
dbo:wikiPageWikiLink
dbp:chromaticIndex
  • n − 1 (en)
dbp:chromaticNumber
  • see in the article (en)
dbp:degree
  • n − 1 (en)
dbp:genus
  • see in the article (en)
dbp:girth
  • 6 (xsd:integer)
dbp:imageCaption
  • The pancake graph P4 can be constructed recursively from 4 copies of P3 by assigning a different element from the set {1, 2, 3, 4} as a suffix to each copy. (en)
dbp:name
  • Pancake graph (en)
dbp:notation
  • Pn (en)
dbp:properties
dbp:wikiPageUsesTemplate
dcterms:subject
rdfs:comment
  • In the mathematical field of graph theory, the pancake graph Pn or n-pancake graph is a graph whose vertices are the permutations of n symbols from 1 to n and its edges are given between permutations transitive by prefix reversals. The pancake graph of dimension n, Pn, is a regular graph with vertices. Its degree is n − 1, hence, according to the handshaking lemma, it has edges. Pn can be constructed recursively from n copies of Pn−1, by assigning a different element from the set {1, 2, …, n} as a suffix to each copy. (en)
rdfs:label
  • Pancake graph (en)
owl:sameAs
prov:wasDerivedFrom
foaf:depiction
foaf:isPrimaryTopicOf
is dbo:wikiPageWikiLink of
is foaf:primaryTopic of
Powered by OpenLink Virtuoso    This material is Open Knowledge     W3C Semantic Web Technology     This material is Open Knowledge    Valid XHTML + RDFa
This content was extracted from Wikipedia and is licensed under the Creative Commons Attribution-ShareAlike 3.0 Unported License