Rotational circulant graphs

DOI10.1016/J.DAM.2013.08.044MaRDI QIDQ741752zbMATH OpenOpenAlexFDO

Authors Alison Thomson, Sanming Zhou

Publication date 12 September 2014

Published in Discrete Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

circulant graphFrobenius groupgossipinghexagonal meshbalanced regular Cayley mapFrobenius graphharts

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Connectivity (05C40)

Abstract: A Frobenius group is a transitive permutation group which is not regular but only the identity element can fix two points. Such a group can be expressed as the semi-direct product $G=KtimesH$ of a nilpotent normal subgroup $K$ and another group $H$ fixing a point. A first-kind $G$-Frobenius graph is a connected Cayley graph on $K$ with connection set an $H$-orbit $a^H$ on $K$ that generates $K$, where $H$ has an even order or $a$ is an involution. It is known that the first-kind Frobenius graphs admit attractive routing and gossiping algorithms. A complete rotation in a Cayley graph on a group $G$ with connection set $S$ is an automorphism of $G$ fixing $S$ setwise and permuting the elements of $S$ cyclically. It is known that if the fixed-point set of such a complete rotation is an independent set and not a vertex-cut, then the gossiping time of the Cayley graph (under a certain model) attains the smallest possible value. In this paper we classify all first-kind Frobenius circulant graphs that admit complete rotations, and describe a means to construct them. This result can be stated as a necessary and sufficient condition for a first-kind Frobenius circulant to be 2-cell embeddable on a closed orientable surface as a balanced regular Cayley map. We construct a family of non-Frobenius circulants admitting complete rotations such that the corresponding fixed-point sets are independent and not vertex-cuts. We also give an infinite family of counterexamples to the conjecture that the fixed-point set of every complete rotation of a Cayley graph is not a vertex-cut.

Recommendations

• FROBENIUS CIRCULANT GRAPHS OF VALENCY FOUR
• Gossiping and routing in second-kind Frobenius graphs
• Complete rotations in Cayley graphs
• Frobenius circulant graphs of valency six, Eisenstein-Jacobi networks, and hexagonal meshes
• Permutation groups with a cyclic regular subgroup and arc transitive circulants.

Cites work

• scientific article; zbMATH DE number 4004216 (Why is no real title available?)
• scientific article; zbMATH DE number 47996 (Why is no real title available?)
• scientific article; zbMATH DE number 1054728 (Why is no real title available?)
• scientific article; zbMATH DE number 1467844 (Why is no real title available?)
• scientific article; zbMATH DE number 894528 (Why is no real title available?)
• A Class of Arc-Transitive Cayley Graphs as Models for Interconnection Networks
• A Combinatorial Problem Related to Multimodule Memory Organizations
• A complementary survey on double-loop networks
• A group-theoretic model for symmetric interconnection networks
• A survey on multi-loop networks.
• Complete rotations in Cayley graphs
• Concerning two conjectures on the set of fixed points of a complete rotation of a Cayley digraph
• Dissemination of information in communication networks. Broadcasting, gossiping, leader election, and fault-tolerance.
• FROBENIUS CIRCULANT GRAPHS OF VALENCY FOUR
• Finding optimal routings in Hamming graphs
• Frobenius circulant graphs of valency six, Eisenstein-Jacobi networks, and hexagonal meshes
• Gossiping and routing in second-kind Frobenius graphs
• Gossiping and routing in undirected triple-loop networks
• Graph theory
• Group Action Graphs and Parallel Architectures
• New methods for using Cayley graphs in interconnection networks
• On 4-valent Frobenius circulant graphs
• On forwarding indices of networks
• On orbital regular graphs and Frobenius graphs
• On the Classification of Symmetric Graphs with a Prime Number of Vertices
• On the full automorphism group of a graph
• Performance analysis of virtual cut-through switching in HARTS: a hexagonal mesh multicomputer
• Regular maps from Cayley graphs. I: Balanced Cayley maps
• Skew-morphisms of regular Cayley maps
• Spanning subgraphs with applications to communication of a subclass of the Cayley-graph-based networks
• Symmetry in interconnection networks based on Cayley graphs of permutation groups: A survey
• The Lattice Point Covering Theorem for Rectangles
• The edge-forwarding index or orbital regular graphs
• The isomorphism problem for circulant graphs via Schur ring theory
• Toida's conjecture is true

Cited in

(11)

• Rotation numbers for unions of circuits
• Gossiping and routing in second-kind Frobenius graphs
• FROBENIUS CIRCULANT GRAPHS OF VALENCY FOUR
• Rotation of spatial graphs
• Frobenius circulant graphs of valency six, Eisenstein-Jacobi networks, and hexagonal meshes
• Cores of imprimitive symmetric graphs of order a product of two distinct primes
• Complete rotations in Cayley graphs
• Concerning two conjectures on the set of fixed points of a complete rotation of a Cayley digraph
• On 4-valent Frobenius circulant graphs
• Cyclotomic graphs and perfect codes
• Resolvable Mendelsohn designs and finite Frobenius groups

This page was built for publication: Rotational circulant graphs

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