Independent even cycles in the pancake graph and greedy prefix-reversal Gray codes. (English) Zbl 1349.05198
Summary: The Pancake graph \(P_n\), \(n\geqslant 3\), is a Cayley graph on the symmetric group generated by prefix-reversals. It is known that \(P_n\) contains any \(\ell\)-cycle for \(6\leqslant\ell\leqslant n!\). In this paper we construct a family of maximal (covering) sets of even independent (vertex-disjoint) cycles of lengths \(\ell\) bounded by \(O(n^2)\). We present the new concept of prefix-reversal Gray codes based on independent cycles which extends the known greedy prefix-reversal Gray code constructions given by Zaks and Williams. Cases of non-existence of codes based on the presented family of independent cycles are provided using the fastening cycle approach. We also give necessary condition for existence of greedy prefix-reversal Gray codes based on the independent cycles with arbitrary even lengths.
MSC:
| 05C45 | Eulerian and Hamiltonian graphs |
| 05C25 | Graphs and abstract algebra (groups, rings, fields, etc.) |
| 05C38 | Paths and cycles |
| 90B10 | Deterministic network models in operations research |
Keywords:
pancake graph; pancake sorting; even cycles; disjoint cycle cover; prefix-reversal Gray codes; fastening cycleSoftware:
MathematicaReferences:
| [1] | Gilbert, E.N.: Gray codes and paths on the \[n\] n-cube. Bell Syst. Tech. J. 37, 815-826 (1958) · doi:10.1002/j.1538-7305.1958.tb03887.x |
| [2] | Joichi, J.T., White, D.E., Williamson, S.G.: Combinatorial Gray codes. SIAM J. Comput. 9(1), 130-141 (1980) · Zbl 0452.05009 · doi:10.1137/0209013 |
| [3] | Kanevsky, A., Feng, C.: On the embedding of cycles in Pancake graphs. Parallel Comput. 21, 923-936 (1995) · Zbl 0875.68708 · doi:10.1016/0167-8191(94)00096-S |
| [4] | Konstantinova, E.V., Medvedev, A.N.: Cycles of length seven in the Pancake graph. Diskretn. Anal. Issled. Oper. 17(5), 46-55 (2010). (in Russian) · Zbl 1249.05207 |
| [5] | Konstantinova, E., Medvedev, A.: Small cycles in the Pancake graph. Ars Mathematica Contemporanea 7, 237-246 (2014) · Zbl 1301.05126 |
| [6] | Savage, C.: A survey of combinatorial Gray codes. SIAM Rev. 39, 605-629 (1996) · Zbl 1049.94513 · doi:10.1137/S0036144595295272 |
| [7] | Sheu, J.J., Tan, J.J.M., Hsu, L.H., Lin, M.Y.: On the cycle embedding of Pancake graphs. In: Proceedings of 1999 National Computer Symposium, pp. C414-C419 (1999) · Zbl 0875.68708 |
| [8] | Sheu, J.J., Tan, J.J.M., Chu, K.T.: Cycle embedding in pancake interconnection networks. In: Proceedings of the 23rd Workshop on Combinatorial Mathematics and Computation Theory in Taiwan, pp. 85-92 (2006) |
| [9] | Skiena, S.: Hypercubes, Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica, pp. 148-150. Addison-Wesley, Reading (1990) · Zbl 0786.05004 |
| [10] | Williams, A.: The greedy gray code algorithm. LNCS 8037, 525-536 (2013) · Zbl 1390.68753 |
| [11] | Williams, A., Sawada, J.: Greedy Pancake flipping. Electron. Notes Discrete Math. 44, 357-362 (2013) · doi:10.1016/j.endm.2013.10.056 |
| [12] | Zaks, S.: A new algorithm for generation of permutations. BIT 24, 196-204 (1984) · Zbl 0542.68054 · doi:10.1007/BF01937486 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
