Automorphism groups of the Pancake graphs

DOI10.1016/J.IPL.2011.12.010zbMATH Open1239.05137arXiv1201.0452OpenAlexW2081392540MaRDI QIDQ413293FDOQ413293

Yun-Ping Deng, Xiao-Dong Zhang

Publication date: 4 May 2012

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

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.$

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)

Cites Work

• Symmetry in interconnection networks based on Cayley graphs of permutation groups: A survey
• A group-theoretic model for symmetric interconnection networks
• On the full automorphism group of a graph
• Bounds for sorting by prefix reversal
• Title not available (Why is that?)
• On the Diameter of the Pancake Network
• Efficient dominating sets in Cayley graphs.
• Title not available (Why is that?)
• Graphical Regular Representations of Non-Abelian Groups, I

Cited In (6)

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

   Recommendations

• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• 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 👍 👎

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)