¿^creative , ars mathematica ^commons contemporánea Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.) ARS MATHEMATICA CONTEMPORANEA 7 (2014) 237-246 Small cycles in the Pancake graph Elena Konstantinova * Sobolev Institute of Mathematics, Novosibirsk, 630090, Russia Department of Mathematics, Yeungnam University, 712-749, South Korea Alexey Medvedev Sobolev Institute ofMathematics, Novosibirsk, 630090, Russia Central European University, Budapest, 1051, Hungary Received 17 June 2011, accepted 23 April 2013, published online 26 April 2013 Abstract The Pancake graph is well known because of the open Pancake problem. It has the structure that any l-cycle, 6 < I < n!, can be embedded in the Pancake graph Pn, n > 3. Recently it was shown that there are exactly n independent 6-cycles and n!(n - 3) distinct 7-cycles in the graph. In this paper we characterize all distinct 8-cycles by giving their canonical forms as products of generating elements. It is shown that there are exactly n!(n3+i2ni-i03n+i76) distinct 8-cycles in Pn, n > 4. A maximal set of independent 8-cycles contains n of these. Keywords: Cayley graphs, Pancake graph, cycle embedding, small cycles. Math. Subj. Class.: 05C15, 05C25, 05C38, 90B10 1 Introduction The Pancake graph Pn = (Symn,PR),n > 2, is the Cayley graph on the symmetric group Symn of permutations n = [n1n2... nn], where n = n(i) for any 1 < i < n, with the generating set PR = {n g Symn : 2 < i < n} of all prefix-reversals n reversing the order of any substring [1, i], 2 < i < n, of a permutation n when multiplied on the right, i.e. [n1... nini+1... n„]rj = [n... n1ni+1... nn]. It is a connected vertex-transitive (n-1)-regular graph of order n!. This graph is well known because of the combinatorial Pancake problem which was posed in [4] as the problem of finding its diameter. The problem is still *The research was supported by grant 12-01-00448 of the Russian Foundation of Basic Research. The corresponding author. E-mail addresses: e konsta@math.nsc.ru (Elena Konstantinova), an medvedev@yahoo.com (Alexey Medvedev) ©® This work is licensed under http://creativecommons.org/licenses/by/3.0/ 238 Ars Math. Contemp. 7 (2014) 201-213 open. Some upper and lower bounds [5, 6] as well as exact values for 2 < n < 19 [1,2] are known. One of the main difficulties in solving this problem is the complicated cycle structure of the Pancake graph. This graph is hamiltonian [11] and the following result is also known. Theorem 1.1. [7, 10] All cycles of length l, where 6 < I < n!, can be embedded in the Pancake graph Pn, n > 3, but there are no cycles of length 3,4 or 5. An explicit description of cycles is gradually being developed. The first results concerning cycle characterization in the Pancake graph were obtained in [8] where the following cycle representation via a product of generating elements was used. A sequence of prefix-reversals Cl = ri0 ... ril_1, where 2 < ij < n, and ij = ij+1 for any 0 < j < l — 1, such that nri0 .. .ril_1 = n, where n G Symn, is called a form of a cycle Cl of length l. A cycle Ci of length l is also called an l-cycle, and a vertex of Pn is identified with the permutation which corresponds to this vertex. It is evident that any l-cycle can be presented by 2l forms (not necessarily different) with respect to a vertex and a direction. The canonical form Cl of an l-cycle is called a form with a lexicographically maximal sequence of indices i0 ... il—1. By using this description, the results characterizing 6- and 7-cycles were obtained in [8]. Theorem 1.2. [8] The Pancake graph Pn,n > 3, has n independent 6-cycles of the canonical form C6 = r3r2r3r2r3r2 and n!(n — 3) distinct 7-cycles of the canonical form C7 = rkrk—1rkrk—1rk—2rkr2, where 4 < k < n. Each of the vertices of Pn belongs to exactly one 6-cycle and 7(n — 3) distinct 7-cycles. The main result of this paper is the following theorem. Theorem 1.3. Each of vertices of Pn, n > 4, belongs to N = n3+12n2_,103n+176 distinct 8-cycles of the following canonical forms: C1 — rk rj ri rj rk rk-j+i ri rk—j+i, 2 < i 4. Corollary 1.5. A maximal set of independent 8-cycles in Pn,n > 4, contains n of these. The proof of Theorem 1.3 is based on the hierarchical (recursive) structure of the Pancake graph which can be presented as follows. The graph Pn,n > 3, is constructed E. Konstantinova and A. Medvedev: Small cycles in the Pancake graph 239 from n copies of Pn_i(i), 1 < i < n, such that each Pn_i(i) has the vertex set Vj = j[ni... nn_1i], where nk € {1,..., n}\{i} : 1 < k < n - 1}, |Vj| = (n - 1)!, and the edge set E = {{[n .. .nn_ii], [n .. .nn_ii] j} : 2 < j < n - 1}, |Ej| = (n_i}2(n_2). Any two copies Pn_i(i),Pn_i(j),i = j, are connected by (n - 2)! edges presented as {[in2...n„_ij], [jn„_i...n2i]}, where [in...n„_ij]r„ = [jn„_i...^i]. Prefix-reversals rj, 2 < j < n - 1, define internal edges in all n copies Pn_i(i), 1 < i < n, and the prefix-reversal rn defines external edges between copies. Copies Pn_i(i), or just Pn_i when it is not important to specify the last element of permutations belonging to the copy, are also called (n - 1)-copies. Since P3 = C6 and due to the hierarchical structure, P4 has four copies of P3, each of which obviously cannot contain 8-cycles. However, P4 has 8-cycles consisting of paths within copies of P3 together with external edges between these copies. In general, any 8-cycle of Pn, n > 4, must consist of paths within subgraphs that are isomorphic to Pk_i for some 4 < k < n, joined by external edges between these subgraphs. Hence, all 8-cycles of Pn, n > 4, could be found recursively by considering 8-cycles within each Pk, 4 < k < n, consisting of vertices from some copies of Pk_i. This approach is used in the proof of Theorem 1.3. To get the main result, we also need some technical lemmas concerning paths of length three between vertices of a given form. So, in the next section we introduce additional notations and prove two small lemmas. In Section 3 we prove Theorem 1.3 and its corollaries. 2 Technical lemmas A segment [n ... nj] of a permutation n = [ni... n ... flj ... nn] consists of all elements that lie between n and nj inclusive. Any permutation can be written as a sequence of singleton and multiple segments. We use characters from {p, q, s, t} to denote singletons and characters from {a, 7, A, B, C} to denote multiple segments. If n = [a,0], where a = [nin2... n] and ft = [nj+i... nn], then nr|a| = [a^], where |a| is the number of elements in a segment a, and a is the inversion of a segment a. It is obvious that a = a. Note that we allow empty segments where this does not contradict the initial definitions. An independent set D of vertices in a graph is called an efficient dominating set if each vertex not in D is adjacent to exactly one vertex in D [3]. It is known [9] that Dp = {[pn2 ...nn] : nj € {1,..., n}\{p}, 2 < j < n}, |Dp| = (n - 1)!, 1 < p < n, are efficient dominating sets in Pn, n > 3. Let us note that external edges of Pn are incident to vertices from different efficient dominating sets of Pn. The distance d = d(n, t) between two vertices n, t in Pn is defined as the least number of prefix-reversals transforming n into t, i.e. nrjj ri2 ... rid = t. The next lemma gives a full list of paths of length three between two vertices of the same efficient dominating set. Lemma 2.1. Two permutations n, t € Dp, 1 < p < n, are at distance three from each other in Pn, n > 3, if and only if: 1) either t = nrj rj rj, 2 ^ i < j ^ n, where n = [AB7], t = [AB7 ]; 2) or t = nrjriri_j+i, 2 ^ j < i ^ n, where n = [pABy], t = [pBAy]. Proof. We consider n € Dp such that n = [paq^k], nj = q. Let us find other vertices from Dp being at the distance three from n. Let ni = nrj = [qap^k], where nj = p, 2 < j < n. An application of a prefix-reversal rj, 2 < i < n, i = j, to the permutation ni gives us two cases: either i < j or i > j. 240 Ars Math. Contemp. 7 (2014) 201-213 1) If i < j then n2 = nVj = [a2qa1p,0k], where n2 = p, a = and |a2| = i — 1, and then t = n2rj = [pa1qa2Pkj. Hence t = nrjr^- and we get n = [AB7], t = [AB7] by setting A = pa1, B = a2q, 7 = 0k. Note, that using rj is the only way to restorep to the first position and thus to end at an element of Dp after reaching n2. 2) If i > j then n2 = n1ri = [01paq02k], where n2_j+1 = p, 0 = 0102 and |01| = i — j, and then t = n2rj_j+1 = [p,1 aq,2k]. Hence t = nrjrjrj_j+1 and we get n = [pABy], t = [pBAy] by setting A = aq, B = 01, 7 = 02k. Note, that using rj_j+1 is the only way to restore p to the first position and thus to end at an element of Dp after reaching n2. □ The next lemma gives a description of paths of length three defined on internal edges of the graph between vertices of given forms. Lemma 2.2. Let permutations n and t be presented as: 1) n = [y1ABy2] and t = [y1ABy2], where |y1| > 1, |A| > 2. Then: a) there exists a unique path of length three: t = nr|7i| + |A|r|A|r|7l| + |A|, (2.1) provided that either |y1| > 2 and |A| > 2, or 1711 = 1 and |A| > 3; b) there are two paths of length three: t = nr2 r3r2, t = nr3r2r3, (2.2) provided that 1711 = 1 and |A| = 2; 2) n = [71AB72] andt = [71BA72], where I711 > 0, |A| > 1, |B| > 1. Then: a) there is a unique path of length three: t = nr|7i| + 2r2r|7i|+2, (2.3) provided that 1711 > 2, and |A| = |B| = 1; b) there is a unique path of length three: T = nr|Yi | + | A|r|Yi | + | A| + |B| r|Yi | + |B|, (2.4) provided that 1711 = 1, and |A| = 1 or |B| = 1; c) there are two paths of length three: t = nr2r3r2 = nr3r2r3, (2.5) provided that 1711 = |A| = |B| = 1; d) there is a unique path of length three: T = nr|A| r|A| + |B|r|B|, (2.6) provided that 1711 =0 and |A| > 2, |B| > 2. There are no other paths of length three between n and t of these types. E. Konstantinova and A. Medvedev: Small cycles in the Pancake graph 241 Proof. 1) If n = [71AB72] and t = [71AB72], then (2.1) is checked by a direct verification: [71AB72] |Y1i+|A| [atTb72] ^ [at1b72] Iyi_1+|a| [71AB72]. Suppose that there is one more path of length three. Then these two paths should form a 6-cycle. In part (a), either |71| > 2 and |A| > 2, or |71| = 1 and |A| > 3, so r|7l|+|A| = rm for some m > 4, but by Theorem 1.2, no 6-cycle includes rm with m > 4 in its form. Therefore, the given path is the only one in this case. In part (b), |71| = 1 and |A| = 2, so m = 3 and the condition of Theorem 1.2 holds, hence we obtain two distinct paths of stated forms (2.2). 2) If n = [71AB72] and t = [71BA72], and |71 | > 2, |A| > 1, |B| > 1, then there is the following path of length four between these vertices: n = [71AB72] r 1 1 A 1 [A7TB72] r 1 Yl1 +4 1+1 B 1 [B71A72] r 1 1 B 1 [7IBA72] r^|[71BA72]= t. (2.7) Suppose there is also a path of length three between n and t. By Theorem 1.1, there are no cycles of length 3 or 5, and hence no paths of lengths 3 and 4 exist between two fixed vertices unless the paths are disjoint. This means that these two paths should form a 7-cycle, including the sequence rm+arm+a+brm+brm, where |71| = m, |A| = a and |B| = b. By Theorem 1.2, this is possible only in the case when m = k — 2, k > 4, and a = b =1, which implies that a unique path of length three has the form rm+2r2rm+2 that corresponds to (2.3). Putting |y1 | = 1 in (2.7), a path t — nr|7l |+|A|r|7l|+|A|+|B|r|7l|+|B|, corresponding to (2.4), is obtained. Taking |71| = m, |A| = a and |B | = b, the obtained path is presented as rm+arm+a+brm+b. Suppose that there is one more path of length three between n and t. Then these two paths should form a 6-cycle. By Theorem 1.2, this is possible only in the case when m = a = b = 1, which gives us the paths t = nr2r3r2 and t = nr3r2r3, corresponding to (2.5). Putting |71| =0 in (2.7), a path t = nr|A|r|A|+|B|r|B|, corresponding to (2.6) with |A| > 2, |B| > 2, is obtained. Suppose there is one more path of length three between n and t. Then these two paths should form a 6-cycle. By the conditions of Lemma, |A| + |B| > 4, hence r|A| + |B| = rm for some m > 4, but by Theorem 1.2, no 6-cycle includes rm with m > 4 in its form. Therefore, the given path is the only one in this case. If |A| = 1 or |B| = 1, then the path above is transformed into a 2-path or an edge. This completes the proof of the lemma. □ 3 Proof of Theorem 1.3 To find all 8-cycles passing through the same vertex in Pn, n > 4, we use its hierarchical structure by considering recursively 8-cycles within each copy Pk, 4 < k < n, consisting of vertices from copies of Pk-1. It is assumed that any copy of Pk-1 has at least two vertices, since each vertex has a unique external edge. We obtain canonical forms of 8-cycles and count their numbers. Case 1: an 8-cycle within Pk has vertices from two copies of Pk-1 Suppose that an 8-cycle is formed on vertices from copies Pk-1(p) and Pk-1(s), 1 < p = s < k. It was shown in [8] that if two vertices n and t, belonging the same (k — 1)-copy, are at the distance at most two, then their external neighbours n and t should belong to distinct (k — 1)-copies. Hence, an 8-cycle cannot occur in situations when its two (three) 242 Ars Math. Contemp. 7 (2014) 201-213 r> Pk-l(p) case 1 case 2 Figure 1: (4 + 4)-situation. vertices belong to one copy and six (five) vertices belong to another one. Therefore, such an 8-cycle must have four vertices in each of the two copies. (4 + 4)-situation. Suppose that four vertices of such an 8-cycle belong to a copy Pk-1(s), and other four vertices belong to a copy Pk-1(p). Herewith, four vertices of Pk-1 (s) should form a path of length three whose endpoints should be adjacent to vertices from Pk-1(p), which means both vertices should belong to the efficient dominating set Dp. So, one vertex of Pk-1(s) that is adjacent to a vertex of Pk-1(p) must have the form [paq^s]. By Lemma 2.1, it is not hard to see that this gives rise to two possible forms for the remaining vertices of Pk-1(s). These are given in Figure 1, where |a| = j - 2 and so = k - j - 1. In the first case we also have a = a1a2 and |a2| = i - 1 > 1, while in the second case we also have 1 = i - j > 1 and |^21 = k - i - 1. Denote y1 = s,0, A = qa2, B = a1, y2 = p, where |y1| = + 1 > 1, |A| > 2, |B| > 0, then in the first case npi,nP4 have the forms [y1ABy2] and [y1ABy2]. By Lemma 2.2 (case 1a), there is a unique path of length three between these permutations if |y1| = | + 1 = k - j > 1 and |A| = |a2| + 1 = i > 3, or k - j > 2 and i > 2, and by Lemma 2.2 (case 1b), there are two distinct paths if k - j = 1 and i = 2. Hence, such an 8-cycle has the form Cg = rk-j+irirk-j+irkrjr^jrk, with 2 < i < j < k - 1, 4 < k < n, the canonical form of which corresponds to (1.1). The case of k - j = 1 and i = 2 by symmetry gives one additional form Cg = rfc-1r2rfc-1rfcr2r3r2rk, the canonical form of which corresponds to (1.2). Denote Y1 = s^, A = B = qa, Y2 = p, where |y1 | = |^2| + 1 > 1, |A| = |^1| > 1, |B| = |a| + 1 > 1, then in the second case we have npi = [y1ABy2], nP4 = [y1BAy2]. By Lemma 2.2 (case 2a), there is a unique path of length three between npi and nP4 if |Y11 = k - i > 2, |A| = 1 = i - j = 1 and |B| = |a| + 1 = j - 1 = 1. Hence, j = 2, 1 = 3, and for k > 5 an 8-cycle has the form rk-1r2rfc-1rfcr2r3r2rfc, corresponding again to the canonical form (1.2). By Lemma 2.2 (case 2b), there also exists a unique path of length three between npi and nP4 if |y1 | = k - i = 1, |A| = |^1| = i - j > 1, |B| = |a| + 1 = j - 1 > 1. This means that i = k -1, and such an 8-cycle has the form Cg = rkrk-jrk-1rjrkrk-jrk-1rj, 2 < j < k - 2, the canonical form of which corresponds to (1.3), if we set j = i. So, there E. Konstantinova and A. Medvedev: Small cycles in the Pancake graph 243 Figure 2: (2 + 2 + 4)-situation. is a unique path of length three under the conditions listed, unless |A| = |B| = 1 when by Lemma 2.2 (case 2c) this path is not unique. So, k = 4, j = 2, i = 3 and 8-cycles take forms r2r3r2r4r3r2r3r4 and r3r2r3r4r3r2r3r4, corresponding to forms (1.2) and (1.1). Thus, all 8-cycles occurring in the case of two copies are found. Case 2: an 8-cycle within Pk has vertices from three copies of Pk_1 Suppose an 8-cycle is formed on vertices from copies Pk_1(p), Pk_1(q), Pk_1(s), where 1 < p = q = s < k. There are following possible situations in this case. (2 + 2 + 4)-situation. The distribution of vertices among the copies is presented by Figure 2. Let nsi = [paqfts] where n®1 = q with |a| = i — 2, = k — i — 1. Then nS2, npi, nP2, nqi and nq4 are straightforward to define. Vertices nqi and nq4 differ in the order of segments sft and pa, hence they have the forms [y1AB^2] and [y1BA^2], where Y1 is empty, A = s]3, B = pa, 72 = q and |A| = | + 1 > 1, |B| = |a| + 1 > 1. By Lemma 2.2 (case 2d), between nqi and nq4 there exists a unique path of length three provided that |A| = k — i > 2, |B| = i — 1 > 2, and no path of this length if |A| = 1 or |B| = 1. Thus, an 8-cycle has the form C4 = rkrk_i+1rkri_1rk_1rk_irkri, where 3 < i < k — 2, k > 5, the canonical form of which corresponds to (1.4). (2 + 3 + 3)-situation. The distribution of vertices among the copies is presented by Figure 3. Let nsi = [paqfts], where |a| = i — 2 and = k — i — 1. Then nS2, nPi and nqi are straightforward to define. Since nP3 and nq3 are joined by an external edge, np3 = q. Moreover, npi and nP3 should be joined by a path of length two that can be obtained by two ways: pi r 7; _ c [^2s^1qap] ^ [q&s^ap] = np3, where ^ = 0. npi = [spqap] ^ < 2 I [a2q^s«Yp] ^ [qa^SsaYp] = np'3, where |a2| = 0. From the other side, nq'3 and nP3 are joined by an external edge, hence n\3 = p, and there 244 Ars Math. Contemp. 7 (2014) 201-213 Figure 3: (2 + 3 + 3)-situation. should be a path of length two between nqi and nq3 such that: nqi = [s/3paq] ^ { ^sfiipaq] ^ [p^sfoaq] = nq3, where = 0. I [aip3s®2q] ^ [pai3sa2q] = nq3, where |ai| = 0. Analysis of non-empty segments in these permutations shows that external edges occur between: np3 and nq2, if |a2| = 0, |31| = 0; np3 and nqi, if |ai| = 0, |31| = 0; np3 and nq3, if |3| =0. There is no external edge between nP3 and nq3 since they have the same order of elements in the segment s32. Since |a| = i - 2, |3| = k - i - 1, then using the edge between nP3 and nq3, where |a2| = 0, |31| = 0, we have |a| > 1, |3| > 1, and such an 8-cycle has the form Cf = rkrk-irk-i+i rkri-irk-irkr®, with 3 ^ i ^ k — 2, 5 ^ k ^ n, the canoni- 2 1 cal form of which corresponds to (1.5). Using the external edge between nP3 and nq3, where |ai| = 0, |3i| = 0, we have |a| > 1, |3| > 1, and such an 8-cycle has the form rkrk-iri-irkrk-i+irk-irkr®, where 3 < i < k - 2, the canonical form of which also corresponds to the form (1.5). Finally, using the external edge between nP3 and nq3, where |3| = 0, we have i = k - 1, |ai| = j > 1, |a2| = k - 3 - j > 1, so there is one more 8-cycle of the form Cf = rfcrfc_j_irfc_j_2rfcrj+irj+2rfcrfc-i, where 1 < j < k - 4, 5 < k < n, the canonical form of which corresponds to (1.6), if we put j = i - 1. Thus, all 8-cycles occurring in the case of three copies are found. Case 3: an 8-cycle within Pk has vertices from four copies of Pk-i The distribution of vertices among the copies is presented by Figure 4. Let nqi = [sat3pYq], where |a| > 0, |3| > 0, |y| > 0. There are two cases. 1) Suppose that nqi is adjacent to nsi, and nq2 is adjacent to n*1. Since there is only one cycle edge within each copy, hence this edge is uniquely defined and all vertices' labels are straightforward to obtain (see Figure 4, case 1). Thus, we end up with npi = [sat3qYp], nP2 = [tas3qYp]. If an 8-cycle does exist, then npi, nP2 should be incident to the same E. Konstantinova and A. Medvedev: Small cycles in the Pancake graph 245 Figure 4: (2 + 2 + 2 + 2)-situation. internal edge, and hence, there should exist a prefix-reversal transforming nPl into nP2, namely, r|a|+2. If we set |a| = i - 2, = j - i -1, |y | = k - j -1, where 2 < i < j < k, then such an 8-cycle is presented by the form Cg = rkrk-j+irfcrjrfcrk-j+irkn, where 2 < i < j ^ k - 1, 4 < k < n, the canonical form of which corresponds to (1.7). 2) Suppose that nqi is adjacent to nSl, and nq2 is adjacent to nPl (see Figure 4, case 2), then we end up with n*1 = [saqjpPt], nt2 = [pPq^sat]. In this case, an internal edge between vertices n*1 and nt2 does exist only if |a| = = |y| = 0, which means that k = 4 and such an 8-cycle takes the form (1.8). Therefore, all canonical forms for 8-cycles in Pn, n > 4, are obtained. Now we count the total number N = J2¿=1 NCi of distinct 8-cycles passing through a given vertex, where NCi corresponds to the number of distinct 8-cycles described by the canonical form C|, 1 ^ i ^ 8. Let us note that any canonical form of an /-cycle describes I cycles (not necessarily distinct) for a given vertex. Among all canonical forms (1.1)-(1.8), there is the only one, namely the form (1.5), which describes eight distinct 8-cycles. In other cases, identical forms occur. For example, from the canonical form Cf = r4r3r^rsr^rsr^rs one can get two forms, namely, r4r3r4r3r4r3r4r3 and r3r4r3r4r3r4r3r4 which are identical because they describe the same 8-cycle. Thus, the canonical form C gives the only 8-cycle, hence, NC8 = 1. In other cases, it can be shown in the same manner (by taking into account identical forms) that the numbers NCi, 1 < i < 7, are given as follows: NCi = (n-3)(n-2)(n-1), NC2 = 4(n - 3), NCj = (n - 2)(n - 3), Nc4 = Nc6 = 2(n - 3)(n - 4), N^ = 4(n - 3)(n - 4), Ncj = ("-3)(n62)(n-1). Thus, the total number is given by N = n3 + 12n2 - 103n + 176 = 2 ' which completes the proof of the theorem. □ The total number of distinct 8-cycles in Pn, n > 4, is given by n!(nJ+12n2i6103n+176) since there are n! vertices in the graph each of which belongs to N distinct 8-cycles. This proves Corollary 1.4. 246 Ars Math. Contemp. 7 (2014) 201-213 A maximal set of independent 8-cycles in Pn, n > 4, contains n of these, since P4 has three independent 8-cycles, and there are n copies of P4, each of which consists of exactly three independent 8-cycles. This proves Corollary 1.5. Acknowledgment The authors thank the referees for their critical remarks and valuable suggestions, which helped to improve the quality and clarity of the manuscript. References [1] S. Asai, Y. Kounoike, Y. Shinano and K. Kaneko, Computing the diameter of 17-pancake graph using a PC cluster, LNCS 4128 (2006), 1114-1124. [2] J. Cibulka, On average and highest number of flips in pancake sorting, Theoretical Computer Science 412 (2011), 822-834. [3] I. J. Dejter, O. Serra, Efficient dominating sets in Cayley graphs, Discrete Appl. Math. 129 (2003), 319-328. [4] H. Dweighter, E 2569 in: Elementary problems and solutions, Amer. Math. Monthly 82 (1975) 1010. [5] W. H. Gates and C. H. Papadimitriou, Bounds for sorting by prefix-reversal, Discrete Math. 27 (1979), 47-57. [6] M. H. Hyedari and I. H. Sudborough, On the diameter of the pancake network, Journal of Algorithms 25 (1997), 67-94. [7] A. Kanevsky and C. Feng, On the embedding of cycles in pancake graphs, Parallel Computing 21 (1995), 923-936. [8] E. V. Konstantinova and A. N. Medvedev, Cycles of length seven in the Pancake graph, Diskretn. Anal. Issled. Oper. 17 (2010), 46-55 (in Russian). [9] Ke Qiu, Optimal broadcasting algorithms for multiple messages on the star and pancake graphs using minimum dominating sets, Congress. Numerantium. 181 (2006), 33-39. [10] J. J. Sheu, J. J. M. Tan and K. T. Chu, Cycle embedding in pancake interconnection networks, Proc. 23rd Workshop on Combinatorial Mathematics and Computation Theory, Taiwan (2006), pp. 85-92. [11] S. Zaks, A new algorithm for generation of permutations, BIT 24 (1984), 196-204.