Automorphism groups of the Pancake graphs

DOI10.1016/J.IPL.2011.12.010zbMATH1239.05137OpenAlexW2081392540MaRDI QIDQ413293FDOQ413293

Authors Yun-Ping Deng, Xiao-Dong Zhang

Publication date 4 May 2012

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1201.0452

zbMATH Keywords

automorphism groupinterconnection networkspancake graphefficient dominating sets

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Network design and communication in computer systems (68M10) Graph designs and isomorphic decomposition (05C51)

Abstract: It is well-known that the pancake graphs are widely used as models for interconnection networks cite{Akers}. In this paper, some properties of the pancake graphs are investigated. We first prove that the pancake graph, denoted by $P_n(ngeq4),$ is super-connected and hyper-connected. Further, we study the symmetry of $P_n$ and completely determine its full automorphism group,which shows that $P_n(ngeq5)$ is a graphical regular representation of $S_n.$

Recommendations

• Publication:4735320
• scientific article; zbMATH DE number 3851135
• Automorphism groups of some classes of graphs
• The automorphism group of finite graphs
• The automorphism group of a graphon
• Automorphism groups of geometrically represented graphs
• Automorphism groups of covering graphs
• Automorphism groups of Paley graphs and cyclotomic schemes
• On automorphism groups of some PCS graphs
• The automorphism group of the alternating group graph

Cites work

• scientific article; zbMATH DE number 5139470 (Why is no real title available?)
• scientific article; zbMATH DE number 3823850 (Why is no real title available?)
• A group-theoretic model for symmetric interconnection networks
• Bounds for sorting by prefix reversal
• Efficient dominating sets in Cayley graphs.
• Graphical Regular Representations of Non-Abelian Groups, I
• On the Diameter of the Pancake Network
• On the full automorphism group of a graph
• Symmetry in interconnection networks based on Cayley graphs of permutation groups: A survey

Cited in

(6)

• Some properties of alternating group networks
• Automorphism group of the varietal hypercube graph
• Fault tolerant supergraphs with automorphisms
• Automorphism group of the complete transposition graph
• Automorphism group of the complete alternating group graph
• Automorphism groups of Cayley graphs generated by block transpositions and regular Cayley maps

This page was built for publication: Automorphism groups of the Pancake graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q413293)