Editing Pancake sorting (section)

==Pancake graphs==
[[File:Pancake graph g3.svg|thumb|The pancake graph P<sub>3</sub>]]
[[File:Pancake graph g4.svg|thumb|The pancake graph P<sub>4</sub> can be constructed recursively from 4 copies of P<sub>3</sub> by assigning a different element from the set {1, 2, 3, 4} as a suffix to each copy.]]
{{main|Pancake graph}}
An '''''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. It is a [[regular graph]] with n! vertices, its degree is n&minus;1. The pancake sorting problem and the problem to obtain the [[Diameter (graph theory)|diameter]] of the pancake graph are equivalent.<ref name="pancake17">{{cite conference
 | last1 = Asai | first1 = Shogo
 | last2 = Kounoike | first2 = Yuusuke
 | last3 = Shinano | first3 = Yuji
 | last4 = Kaneko | first4 = Keiichi
 | editor1-last = Nagel | editor1-first = Wolfgang E.
 | editor2-last = Walter | editor2-first = Wolfgang V.
 | editor3-last = Lehner | editor3-first = Wolfgang
 | contribution = Computing the diameter of 17-pancake graph using a PC cluster
 | doi = 10.1007/11823285_117
 | pages = 1114–1124
 | publisher = Springer
 | series = Lecture Notes in Computer Science
 | title = Euro-Par 2006, Parallel Processing, 12th International Euro-Par Conference, Dresden, Germany, August 28 – September 1, 2006, Proceedings
 | volume = 4128
 | year = 2006| isbn = 978-3-540-37783-2
 }}</ref>

The pancake graph of dimension ''n'', P<sub>n</sub> can be constructed recursively from n copies of P<sub>n&minus;1</sub>, by assigning a different element from the set {1, 2, …, n} as a suffix to each copy.

Their [[Girth (graph theory)|girth]]:

:<math>g(P_n) = 6 \text{, if } n>2</math>.

The &gamma;(P<sub>n</sub>) [[graph embedding|genus]] of P<sub>n</sub> is:<ref name="ongenus">{{Cite journal|last1=Nguyen|first1=Quan|last2=Bettayeb|first2=Said|date=2009-11-05|title=On the Genus of Pancake Network.|url=http://ccis2k.org/iajit/PDF/vol.8,no.3/1247.pdf |journal=The International Arab Journal of Information Technology |volume=8|issue=3|pages=289–292}}</ref>

:<math>n!\left( \frac{n-4}{6} \right)+1 \le \gamma(P_n) \le n!\left( \frac{n-3}{4} \right)-\frac{n}{2}+1 </math>

Since pancake graphs have many interesting properties such as symmetric and recursive structures, small degrees and diameters compared against the size of the graph, much attention is paid to them as a model of interconnection networks for parallel computers.<ref>{{Cite journal|last1=Akl|first1=S.G.|last2=Qiu|first2=K.|last3=Stojmenović|first3=I.|date=1993|title=Fundamental algorithms for the star and pancake interconnection networks with applications to computational geometry.|journal=Networks|volume=23|issue=4|pages=215–225|doi=10.1002/net.3230230403|citeseerx=10.1.1.363.4949}}</ref><ref>{{Cite journal|last1=Bass|first1=D.W.|last2=Sudborough|first2=I.H.|date=March 2003|title=Pancake problems with restricted prefix reversals and some corresponding Cayley networks.|journal=Journal of Parallel and Distributed Computing |volume=63|issue=3|pages=327–336|doi=10.1016/S0743-7315(03)00033-9|citeseerx=10.1.1.27.7009}}</ref><ref>{{Cite journal|last1=Berthomé|first1=P.|last2=Ferreira|first2=A.|last3=Perennes|first3=S.|date=December 1996|title=Optimal information dissemination in star and pancake networks.|journal=IEEE Transactions on Parallel and Distributed Systems|volume=7|issue=12|pages=1292–1300|doi=10.1109/71.553290|citeseerx=10.1.1.44.6681}}</ref> When we regard the pancake graphs as the model of the interconnection networks, the diameter of the graph is a measure that represents the delay of communication.<ref>{{cite book|last1=Kumar|first1=V.|last2=Grama|first2=A.|last3=Gupta|first3=A.|last4=Karypis|first4=G.|title=Introduction to Parallel Computing: Design and Analysis of Algorithms|publisher=Benjamin/Cummings|date=1994}}</ref><ref>{{cite book|last=Quinn|first=M.J.|title=Parallel Computing: Theory and Practice|edition=second|publisher=McGraw-Hill|date=1994}}</ref>

The pancake graphs are [[Cayley graph]]s (thus are [[Vertex-transitive graph|vertex-transitive]]) and are especially attractive for parallel processing. They have sublogarithmic degree and diameter, and are relatively [[Dense graph|sparse]] (compared to e.g. [[Hypercube graph|hypercubes]]).<ref name="ongenus"/>