Pancake graph

Pancake graph
Pancake graph
	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.
Vertices
Edges
Girth	6, if n > 2
Chromatic number	see in the article
Chromatic index	n− 1
Genus	see in the article
Properties	Regular ; Hamiltonian ; Cayley ; Vertex-transitive ; Maximally connected ; Super-connected ; Hyper-connected
Notation	Pn
	Table of graphs and parameters

Last updated August 25, 2024

In the mathematical field of graph theory, the pancake graphP_n 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.^[1]

The pancake graph of dimension n, P_n, is a regular graph with $n!$ vertices. Its degree is n − 1, hence, according to the handshaking lemma, it has ${\dfrac {1}{2}}~n!\left(n-1\right)$ edges. P_n can be constructed recursively from n copies of P_n−1, by assigning a different element from the set {1, 2, …, n} as a suffix to each copy.

Results

P_n (n ≥ 4) is super-connected and hyper-connected.^[2]

Their girth is^[3]

g(P_{n})=6,{\text{ if }}n>2.

The γ(P_n) genus of P_n is bounded below and above by:^[4]^[5]

n!\left({\frac {n-4}{6}}\right)+1\leq \gamma (P_{n})\leq n!\left({\frac {3n-10}{12}}\right)+1.

Chromatic properties

There are some known graph coloring properties of pancake graphs.

A P_n (n ≥ 3) pancake graph has total chromatic number $\chi _{t}(P_{n})=n$ , chromatic index $\chi _{e}(P_{n})=n-1$ .^[6]

There are effective algorithms for the proper (n−1)-coloring and total n-coloring of pancake graphs.^[6]

For the $\chi (P_{n})$ chromatic number the following limits are known:

If $4\leq n\leq 8$ , then

\chi (P_{n})\leq {\begin{cases}n-k,&{\text{if }}n\equiv k{\pmod {4}},k=1,3;\\n-2,&{\text{if }}n\equiv k{\pmod {4}},k=0,2;\end{cases}}

if $9\leq n\leq 16$ , then

\chi (P_{n})\leq {\begin{cases}n-(k+2),&{\text{if }}n\equiv k{\pmod {4}},k=1,3;\\n-4,&{\text{if }}n\equiv k{\pmod {4}},k=0,2;\end{cases}}

if $n\geq 17$ , then

\chi (P_{n})\leq {\begin{cases}n-(k+4),&{\text{if }}n\equiv k{\pmod {4}},k=1,2,3;\\n-8,&{\text{if }}n\equiv k{\pmod {4}},k=0.\end{cases}}

The following table discusses specific chromatic number values for some small n.

Specific, or probable values of the chromatic number
$n$	3	4	5	6	7	8	9	10	11	12	13	14	15	16
$\chi (P_{n})$	2	3	3	4	4	4?	4?	4?	4?	4?	4?	4?	4?	4?

Cycle enumeration

In a P_n (n ≥ 3) pancake graph there is always at least one cycle of length ℓ, when $6\leq \ell \leq n!$ (but there are no cycles of length 3, 4 or 5).^[7] It implies that the graph is Hamiltonian and any two vertices can be joined by a Hamiltonian path.

About the 6-cycles of the P_n (n ≥ 4) pancake graph: every vertex belongs to exactly one 6-cycle. The graph contains ${\frac {n!}{6}}$ independent (vertex-disjoint) 6-cycles.^[8]

About the 7-cycles of the P_n (n ≥ 4) pancake graph: every vertex belongs to $7\cdot (n-3)$ 7-cycles. The graph contains $n!\cdot (n-3)$ different 7-cycles.^[9]

About the 8-cycles of the P_n (n ≥ 4) pancake graph: the graph contains ${\frac {n!(n^{3}+12n^{2}-103n+176)}{16}}$ different 8-cycles; a maximal set of independent 8-cycles contains ${\frac {n!}{8}}$ of those.^[8]

Diameter

The pancake sorting problem (obtaining the pancake number) and obtaining the diameter of the pancake graph are equivalents. One of the main difficulties in solving this problem is the complicated cycle structure of the pancake graph.

Pancake numbers
(sequence A058986 in the OEIS )
$n$	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17
$P_{n}$	0	1	3	4	5	7	8	9	10	11	13	14	15	16	17	18	19

The pancake number, which is the minimum number of flips required to sort any stack of $n$ pancakes has been shown to lie between $.mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num{display:block;line-height:1em;margin:0.0em 0.1em;border-bottom:1px solid}.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0.1em 0.1em}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);clip-path:polygon(0px 0px,0px 0px,0px 0px);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}⁠15/14⁠n$ and $⁠ 18 / 11 ⁠ n$ (approximately 1.07n and 1.64n,) but the exact value remains an open problem.^[10]

In 1979, Bill Gates and Christos Papadimitriou ^[11] gave an upper bound of $⁠ 5 / 3 ⁠ n$ . This was improved, thirty years later, to $⁠ 18 / 11 ⁠ n$ by a team of researchers at the University of Texas at Dallas, led by Founders Professor Hal Sudborough ^[12] (Chitturi et al., 2009^[13]).

In 2011, Laurent Bulteau, Guillaume Fertin, and Irena Rusu^[14] proved that the problem of finding the shortest sequence of flips for a given stack of pancakes is NP-hard, thereby answering a question that had been open for over three decades.

Burnt pancake graph

In a variation called the burnt pancake problem, the bottom of each pancake in the pile is burnt, and the sort must be completed with the burnt side of every pancake down. It is a signed permutation, and if a pancake i is "burnt side up" a negative element i` is put in place of i in the permutation. The burnt pancake graph is the graph representation of this problem.

A $P'_{n}$ burnt pancake graph is regular, its order is $2^{n}\cdot n!$ , its degree is $n$ .

For its variant David S. Cohen (best known by his pen name "David X. Cohen") and Manuel Blum proved in 1995, that $3n/2\leq P'_{n}\leq 2n-2$ (when the upper limit is only true if $n>9$ ).^[15]

Burnt pancake numbers
(sequence A078941 in the OEIS )
$n$	1	2	3	4	5	6	7	8	9	10	11	12
$P'_{n}$	1	4	6	8	10	12	14	15	17	18	19	21

The girth of a burnt pancake graph is:^[3]

g(P_{n})=8{\text{, if }}n>2.

Other classes of pancake graphs

Both in the original pancake sorting problem and the burnt pancake problem, prefix reversal was the operation connecting two permutations. If we allow non-prefixed reversals (as if we were flipping with two spatulas instead of one) then four classes of pancake graphs can be defined. Every pancake graph embeds in all higher-order pancake graphs of the same family.^[3]

Classes of pancake graphs
Name	Notation	Explanation	Order	Degree	Girth (if n>2)
unsigned prefix reversal graph	$UP_{n}$	The original pancake sorting problem	$n!$	$n-1$	$6$
unsigned reversal graph	$UR_{n}$	The original problem with two spatulas	$n!$	${n \choose 2}$	$4$
signed prefix reversal graph	$SP_{n}$	The burnt pancake problem	$2^{n}\cdot n!$	$n$	$8$
signed reversal graph	$SR_{n}$	The burnt pancake problem with two spatulas	$2^{n}\cdot n!$	${n+1 \choose 2}$	$4$

Applications

Since pancake graphs have many interesting properties such as symmetric and recursive structures (they are Cayley graphs, thus are vertex-transitive), sublogarithmic degree and diameter, and are relatively sparse (compared to e.g. hypercubes), much attention is paid to them as a model of interconnection networks for parallel computers.^[4]^[16]^[17]^[18] 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.^[19]^[20]

Pancake flipping has biological applications as well, in the field of genetic examinations. In one kind of large-scale mutations, a large segment of the genome gets reversed, which is analogous to the burnt pancake problem.

Related Research Articles

The Collatz conjecture is one of the most famous unsolved problems in mathematics. The conjecture asks whether repeating two simple arithmetic operations will eventually transform every positive integer into 1. It concerns sequences of integers in which each term is obtained from the previous term as follows: if the previous term is even, the next term is one half of the previous term. If the previous term is odd, the next term is 3 times the previous term plus 1. The conjecture is that these sequences always reach 1, no matter which positive integer is chosen to start the sequence. The conjecture has been shown to hold for all positive integers up to 2.95×10²⁰, but no general proof has been found.

In analytic number theory and related branches of mathematics, a complex-valued arithmetic function $:\mathbb {Z} \rightarrow \mathbb {C} }$ is a Dirichlet character of modulus if for all integers $and :$

$that is, is completely multiplicative.$
$; that is, is periodic with period .$

In modular arithmetic, a number $g$ is a primitive root modulo $n$ if every number $a$ coprime to $n$ is congruent to a power of $g$ modulo $n$ . That is, $g$ is a primitive root modulo $n$ if for every integer $a$ coprime to $n$ , there is some integer $k$ for which $g$ ^$k$ ≡ $a$ . Such a value $k$ is called the index or discrete logarithm of $a$ to the base $g$ modulo $n$ . So $g$ is a primitive root modulo $n$ if and only if $g$ is a generator of the multiplicative group of integers modulo $n$ .

In theoretical computer science and cryptography, a trapdoor function is a function that is easy to compute in one direction, yet difficult to compute in the opposite direction without special information, called the "trapdoor". Trapdoor functions are a special case of one-way functions and are widely used in public-key cryptography.

In algebra and number theory, Wilson's theorem states that a natural number n > 1 is a prime number if and only if the product of all the positive integers less than n is one less than a multiple of n. That is, the factorial $satisfies$

In mathematics, a Cunningham chain is a certain sequence of prime numbers. Cunningham chains are named after mathematician A. J. C. Cunningham. They are also called chains of nearly doubled primes.

In number theory, a Wieferich prime is a prime number p such that p² divides $2 p - 1 - 1$ , therefore connecting these primes with Fermat's little theorem, which states that every odd prime p divides $2 p - 1 - 1$ . Wieferich primes were first described by Arthur Wieferich in 1909 in works pertaining to Fermat's Last Theorem, at which time both of Fermat's theorems were already well known to mathematicians.

In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices are of the same color; this is called a vertex coloring. Similarly, an edge coloring assigns a color to each edge so that no two adjacent edges are of the same color, and a face coloring of a planar graph assigns a color to each face or region so that no two faces that share a boundary have the same color.

<span class="mw-page-title-main">Pancake sorting</span> Mathematics problem

Pancake sorting is 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. In this form, the problem was first discussed by American geometer Jacob E. Goodman. A variant of the problem is concerned with burnt pancakes, where each pancake has a burnt side and all pancakes must, in addition, end up with the burnt side on bottom.

In number theory, the Ankeny–Artin–Chowla congruence is a result published in 1953 by N. C. Ankeny, Emil Artin and S. Chowla. It concerns the class number h of a real quadratic field of discriminant d > 0. If the fundamental unit of the field is

In graph theory, total coloring is a type of graph coloring on the vertices and edges of a graph. When used without any qualification, a total coloring is always assumed to be proper in the sense that no adjacent edges, no adjacent vertices and no edge and either endvertex are assigned the same color. The total chromatic number χ″(G) of a graph G is the fewest colors needed in any total coloring of G.

In number theory, the Kronecker symbol, written as $or, is a generalization of the Jacobi symbol to all integers . It was introduced by Leopold Kronecker.$

Gauss's lemma in number theory gives a condition for an integer to be a quadratic residue. Although it is not useful computationally, it has theoretical significance, being involved in some proofs of quadratic reciprocity.

The faro shuffle (American), weave shuffle (British), or dovetail shuffle is a method of shuffling playing cards, in which half of the deck is held in each hand with the thumbs inward, then cards are released by the thumbs so that they fall to the table interleaved. Diaconis, Graham, and Kantor also call this the technique, when used in magic.

In graph theory, circular coloring is a kind of coloring that may be viewed as a refinement of the usual graph coloring. The circular chromatic number of a graph $, denoted can be given by any of the following definitions, all of which are equivalent.$

$is the infimum over all real numbers so that there exists a map from to a circle of circumference 1 with the property that any two adjacent vertices map to points at distance along this circle.$
$is the infimum over all rational numbers so that there exists a map from to the cyclic group with the property that adjacent vertices map to elements at distance apart.$
In an oriented graph, declare the imbalance of a cycle $to be divided by the minimum of the number of edges directed clockwise and the number of edges directed counterclockwise. Define the imbalance of the oriented graph to be the maximum imbalance of a cycle. Now, is the minimum imbalance of an orientation of .$

In graph theory, the generalized Petersen graphs are a family of cubic graphs formed by connecting the vertices of a regular polygon to the corresponding vertices of a star polygon. They include the Petersen graph and generalize one of the ways of constructing the Petersen graph. The generalized Petersen graph family was introduced in 1950 by H. S. M. Coxeter and was given its name in 1969 by Mark Watkins.

The graph coloring game is a mathematical game related to graph theory. Coloring game problems arose as game-theoretic versions of well-known graph coloring problems. In a coloring game, two players use a given set of colors to construct a coloring of a graph, following specific rules depending on the game we consider. One player tries to successfully complete the coloring of the graph, when the other one tries to prevent him from achieving it.

In graph theory, the act of coloring generally implies the assignment of labels to vertices, edges or faces in a graph. The incidence coloring is a special graph labeling where each incidence of an edge with a vertex is assigned a color under certain constraints.

In mathematics, specifically in number theory, Newman's conjecture is a conjecture about the behavior of the partition function modulo any integer. Specifically, it states that for any integers $m$ and $r$ such that $, the value of the partition function satisfies the congruence for infinitely many non-negative integers n . It was formulated by mathematician Morris Newman in 1960. It is unsolved as of 2020.$

In mathematics, a queen's graph is an undirected graph that represents all legal moves of the queen—a chess piece—on a chessboard. In the graph, each vertex represents a square on a chessboard, and each edge is a legal move the queen can make, that is, a horizontal, vertical or diagonal move by any number of squares. If the chessboard has dimensions $, then the induced graph is called the queen's graph.$

References

↑ Asai, Shogo; Kounoike, Yuusuke; Shinano, Yuji; Kaneko, Keiichi (2006). "Computing the diameter of 17-pancake graph using a PC cluster". In Nagel, Wolfgang E.; Walter, Wolfgang V.; Lehner, Wolfgang (eds.). Euro-Par 2006, Parallel Processing, 12th International Euro-Par Conference, Dresden, Germany, August 28 – September 1, 2006, Proceedings. Lecture Notes in Computer Science. Vol. 4128. Springer. pp. 1114–1124. doi:10.1007/11823285_117. ISBN 978-3-540-37783-2.
↑ Deng, Yun-Ping; Xiao-Dong, Zhang (March 31, 2012). "Automorphism Groups of the Pancake Graphs". Information Processing Letters. 112 (7): 264–266. arXiv: 1201.0452 . doi:10.1016/j.ipl.2011.12.010. S2CID 38229793.
1 2 3 Compeau, Phillip E.C. (September 6, 2011). "Girth of pancake graphs". Discrete Applied Mathematics. 159 (15): 1641–1645. doi: 10.1016/j.dam.2011.06.013 .
1 2 Nguyen, Quan; Bettayeb, Said (November 5, 2009). "On the Genus of Pancake Network" (PDF). The International Arab Journal of Information Technology. 8 (3): 289–292.
↑ Blanco, Saúl; Buehrle, Charles (June 20, 2023). "Bounds on the genus for 2-cell embeddings of prefix-reversal graphs". arXiv: 2306.11295 [math.CO].
1 2 Konstantinova, Elena (August 1, 2017). "Chromatic Properties of the Pancake Graphs". Discussiones Mathematicae Graph Theory. 37 (3): 777–787. doi: 10.7151/dmgt.1978 .
↑ Sheu, Jyh-Jian; Tan, Jimmy J. M. (2006). "Cycle embedding in pancake interconnection networks" (PDF). The 23rd Workshop on Combinatorial Mathematics and Computation Theory.
1 2 Konstantinova, E.V.; Medvedev, A.N. (April 26, 2013). "Small cycles in the Pancake graph". Ars Mathematica Contemporanea. 7: 237–246. doi: 10.26493/1855-3974.214.0e8 .
↑ Konstantinova, E.V.; Medvedev, A.N. (April 1, 2010). "Cycles of length seven in the pancake graph". Diskretn. Anal. Issled. Oper. 17 (5): 46–55. doi: 10.1016/j.tcs.2008.04.045 .
↑ Fertin, G. and Labarre, A. and Rusu, I. and Tannier, E. and Vialette, S. (2009). Combinatorics of Genome Rearrangements. The MIT Press. ISBN 9780262062824.{{cite book}}: CS1 maint: multiple names: authors list (link)
↑ Gates, W.; Papadimitriou, C. (1979). "Bounds for Sorting by Prefix Reversal". Discrete Mathematics . 27: 47–57. doi: 10.1016/0012-365X(79)90068-2 .
↑ "Team Bests Young Bill Gates With Improved Answer to So-Called Pancake Problem in Mathematics". University of Texas at Dallas News Center. September 17, 2008. Archived from the original on 2012-02-14. Retrieved 2008-11-10. A team of UT Dallas computer science students and their faculty adviser have improved upon a longstanding solution to a mathematical conundrum known as the pancake problem. The previous best solution, which stood for almost 30 years, was devised by Bill Gates and one of his Harvard instructors, Christos Papadimitriou, several years before Microsoft was established.
↑ Chitturi, B.; Fahle, W.; Meng, Z.; Morales, L.; Shields, C. O.; Sudborough, I. H.; Voit, W. (August 31, 2009). "An (18/11)n upper bound for sorting by prefix reversals". Theoretical Computer Science. Graphs, Games and Computation: Dedicated to Professor Burkhard Monien on the Occasion of his 65th Birthday. 410 (36): 3372–3390. doi: 10.1016/j.tcs.2008.04.045 .
↑ Bulteau, Laurent; Fertin, Guillaume; Rusu, Irena (2015). "Pancake Flipping Is Hard". Journal of Computer and System Sciences. 81 (8): 1556–1574. arXiv: 1111.0434 . doi:10.1016/j.jcss.2015.02.003.
↑ David S. Cohen, Manuel Blum: On the problem of sorting burnt pancakes. In: Discrete Applied Mathematics. 61, Nr. 2, 1995, S. 105–120. DOI:10.1016/0166-218X(94)00009-3.
↑ Akl, S.G.; Qiu, K.; Stojmenović, I. (1993). "Fundamental algorithms for the star and pancake interconnection networks with applications to computational geometry". Networks. 23 (4): 215–225. CiteSeerX 10.1.1.363.4949 . doi:10.1002/net.3230230403.
↑ Bass, D.W.; Sudborough, I.H. (March 2003). "Pancake problems with restricted prefix reversals and some corresponding Cayley networks". Journal of Parallel and Distributed Computing. 63 (3): 327–336. CiteSeerX 10.1.1.27.7009 . doi:10.1016/S0743-7315(03)00033-9.
↑ Berthomé, P.; Ferreira, A.; Perennes, S. (December 1996). "Optimal information dissemination in star and pancake networks". IEEE Transactions on Parallel and Distributed Systems. 7 (12): 1292–1300. CiteSeerX 10.1.1.44.6681 . doi:10.1109/71.553290.
↑ Kumar, V., Grama, A., Gupta, A., Karypis, G.: Introduction to Parallel Computing: Design and Analysis of Algorithms. Benjamin/Cummings (1994)
↑ Quinn, M.J.: Parallel Computing: Theory and Practice, second edition. McGraw Hill (1994)

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[pancake17-1] Asai, Shogo; Kounoike, Yuusuke; Shinano, Yuji; Kaneko, Keiichi (2006). "Computing the diameter of 17-pancake graph using a PC cluster". In Nagel, Wolfgang E.; Walter, Wolfgang V.; Lehner, Wolfgang (eds.). Euro-Par 2006, Parallel Processing, 12th International Euro-Par Conference, Dresden, Germany, August 28 – September 1, 2006, Proceedings. Lecture Notes in Computer Science. Vol. 4128. Springer. pp. 1114–1124. doi:10.1007/11823285_117. ISBN 978-3-540-37783-2.

[Automorphism-2] Deng, Yun-Ping; Xiao-Dong, Zhang (March 31, 2012). "Automorphism Groups of the Pancake Graphs". Information Processing Letters. 112 (7): 264–266. arXiv: 1201.0452 . doi:10.1016/j.ipl.2011.12.010. S2CID 38229793.

[girth-3] 1 2 3 Compeau, Phillip E.C. (September 6, 2011). "Girth of pancake graphs". Discrete Applied Mathematics. 159 (15): 1641–1645. doi: 10.1016/j.dam.2011.06.013 .

[ongenus-4] 1 2 Nguyen, Quan; Bettayeb, Said (November 5, 2009). "On the Genus of Pancake Network" (PDF). The International Arab Journal of Information Technology. 8 (3): 289–292.

[boundsongenus-5] Blanco, Saúl; Buehrle, Charles (June 20, 2023). "Bounds on the genus for 2-cell embeddings of prefix-reversal graphs". arXiv: 2306.11295 [math.CO].

[chromatic-6] 1 2 Konstantinova, Elena (August 1, 2017). "Chromatic Properties of the Pancake Graphs". Discussiones Mathematicae Graph Theory. 37 (3): 777–787. doi: 10.7151/dmgt.1978 .

[Sheu2006CycleEI-7] Sheu, Jyh-Jian; Tan, Jimmy J. M. (2006). "Cycle embedding in pancake interconnection networks" (PDF). The 23rd Workshop on Combinatorial Mathematics and Computation Theory.

[Cycle8-8] 1 2 Konstantinova, E.V.; Medvedev, A.N. (April 26, 2013). "Small cycles in the Pancake graph". Ars Mathematica Contemporanea. 7: 237–246. doi: 10.26493/1855-3974.214.0e8 .

[9] Konstantinova, E.V.; Medvedev, A.N. (April 1, 2010). "Cycles of length seven in the pancake graph". Diskretn. Anal. Issled. Oper. 17 (5): 46–55. doi: 10.1016/j.tcs.2008.04.045 .

[10] Fertin, G. and Labarre, A. and Rusu, I. and Tannier, E. and Vialette, S. (2009). Combinatorics of Genome Rearrangements. The MIT Press. ISBN 9780262062824.{{cite book}}: CS1 maint: multiple names: authors list (link)

[Gates1979-11] Gates, W.; Papadimitriou, C. (1979). "Bounds for Sorting by Prefix Reversal". Discrete Mathematics . 27: 47–57. doi: 10.1016/0012-365X(79)90068-2 .

[Sudborough-12] "Team Bests Young Bill Gates With Improved Answer to So-Called Pancake Problem in Mathematics". University of Texas at Dallas News Center. September 17, 2008. Archived from the original on 2012-02-14. Retrieved 2008-11-10. A team of UT Dallas computer science students and their faculty adviser have improved upon a longstanding solution to a mathematical conundrum known as the pancake problem. The previous best solution, which stood for almost 30 years, was devised by Bill Gates and one of his Harvard instructors, Christos Papadimitriou, several years before Microsoft was established.

[13] Chitturi, B.; Fahle, W.; Meng, Z.; Morales, L.; Shields, C. O.; Sudborough, I. H.; Voit, W. (August 31, 2009). "An (18/11)n upper bound for sorting by prefix reversals". Theoretical Computer Science. Graphs, Games and Computation: Dedicated to Professor Burkhard Monien on the Occasion of his 65th Birthday. 410 (36): 3372–3390. doi: 10.1016/j.tcs.2008.04.045 .

[14] Bulteau, Laurent; Fertin, Guillaume; Rusu, Irena (2015). "Pancake Flipping Is Hard". Journal of Computer and System Sciences. 81 (8): 1556–1574. arXiv: 1111.0434 . doi:10.1016/j.jcss.2015.02.003.

[15] David S. Cohen, Manuel Blum: On the problem of sorting burnt pancakes. In: Discrete Applied Mathematics. 61, Nr. 2, 1995, S. 105–120. DOI:10.1016/0166-218X(94)00009-3.

[16] Akl, S.G.; Qiu, K.; Stojmenović, I. (1993). "Fundamental algorithms for the star and pancake interconnection networks with applications to computational geometry". Networks. 23 (4): 215–225. CiteSeerX 10.1.1.363.4949 . doi:10.1002/net.3230230403.

[17] Bass, D.W.; Sudborough, I.H. (March 2003). "Pancake problems with restricted prefix reversals and some corresponding Cayley networks". Journal of Parallel and Distributed Computing. 63 (3): 327–336. CiteSeerX 10.1.1.27.7009 . doi:10.1016/S0743-7315(03)00033-9.

[18] Berthomé, P.; Ferreira, A.; Perennes, S. (December 1996). "Optimal information dissemination in star and pancake networks". IEEE Transactions on Parallel and Distributed Systems. 7 (12): 1292–1300. CiteSeerX 10.1.1.44.6681 . doi:10.1109/71.553290.

[19] Kumar, V., Grama, A., Gupta, A., Karypis, G.: Introduction to Parallel Computing: Design and Analysis of Algorithms. Benjamin/Cummings (1994)

[20] Quinn, M.J.: Parallel Computing: Theory and Practice, second edition. McGraw Hill (1994)

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

Pancake graph
The pancake graph P₄ can be constructed recursively from 4 copies of P₃ by assigning a different element from the set {1, 2, 3, 4} as a suffix to each copy.
Vertices	$n!$
Edges	${\dfrac {1}{2}}~n!\left(n-1\right)$
Girth	6, if n > 2
Chromatic number	see in the article
Chromatic index	n− 1
Genus	see in the article
Properties	Regular Hamiltonian Cayley Vertex-transitive Maximally connected Super-connected Hyper-connected
Notation	P_n
Table of graphs and parameters