Automorphism groups of the Pancake graphs. (English) Zbl 1239.05137
Summary: It is well known that the Pancake graph is widely used as models for interconnection networks. In this paper we prove that the automorphism group of the Pancake graph \(P_n, n\geqslant 5\), is the left regular representation of the symmetric group \(S_n\).
MSC:
| 05C69 | Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) |
| 05C51 | Graph designs and isomorphic decomposition |
| 68R10 | Graph theory (including graph drawing) in computer science |
| 68M10 | Network design and communication in computer systems |
References:
| [1] | Akers, S. B.; Krishnamurthy, B., A group-theoretic model for symmetric interconnection networks, IEEE Trans. Comput., 38, 4, 555-566 (1989) · Zbl 0678.94026 |
| [2] | Dejter, I. J.; Serra, O., Efficient dominating sets in Cayley graphs, Discrete Appl. Math., 129, 319-328 (2003) · Zbl 1035.05060 |
| [3] | Dweighter, H., E 2569, Elementary Problems and Solutions. Elementary Problems and Solutions, Amer. Math. Monthly, 82, 1, 1010 (1975) |
| [4] | Konstantinova, E., Perfect codes in the Pancake networks, available at: |
| [5] | Gates, W. H.; Papadimitriou, C. H., Bounds for sorting by prefix-reversal, Discrete Math., 27, 47-57 (1979) · Zbl 0397.68062 |
| [6] | Godsil, C. D., On the full automorphism group of a graph, Combinatorica, 1, 243-256 (1981) · Zbl 0489.05028 |
| [7] | Hyedari, M. H.; Sudborough, I. H., On the diameter of the Pancake network, J. Algorithms, 25, 1, 67-94 (1997) · Zbl 0888.68007 |
| [8] | Lakshmivarahan, S.; Jwo, J. S.; Dhall, S. K., Symmetry in interconnection networks based on Cayley graphs of permutation groups: A survey, Parallel Comput., 19, 4, 361-407 (1993) · Zbl 0777.05064 |
| [9] | Mckay, B. D., Practical graph isomorphism, Congr. Numer., 30, 45-87 (1981), Nauty available from · Zbl 0521.05061 |
| [10] | Nowitz, L. A.; Watkins, M. E., Graphical regular representations of non-abelian groups, Canad. J. Math., 24, 993-1008 (1972) · Zbl 0249.05122 |
| [11] | Qiu, K., Optimal broadcasting algorithms for multiple messages on the star and Pancake graphs using minimum dominating sets, Congr. Numer., 181, 33-39 (2006) · Zbl 1114.05097 |
| [12] | J.J. Sheu, J.J.M. Tan, L.H. Hsu, M.Y. Lin, On the cycle embedding of Pancake graphs, in: Proceedings of 1999 National Computer Symposium, 1999, pp. 414-419.; J.J. Sheu, J.J.M. Tan, L.H. Hsu, M.Y. Lin, On the cycle embedding of Pancake graphs, in: Proceedings of 1999 National Computer Symposium, 1999, pp. 414-419. |
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.
