Rotational circulant graphs

DOI10.1016/J.DAM.2013.08.044zbMATH Open1300.05125arXiv1302.6652OpenAlexW2087784175MaRDI QIDQ741752FDOQ741752

Authors: Alison Thomson, Sanming Zhou 

Publication date: 12 September 2014

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

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.

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

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.

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)

Cites Work

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

Cited In (11)

• Rotation numbers for unions of circuits
• FROBENIUS CIRCULANT GRAPHS OF VALENCY FOUR
• Gossiping and routing in second-kind Frobenius graphs
• 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
• On 4-valent Frobenius circulant graphs
• Concerning two conjectures on the set of fixed points of a complete rotation of a Cayley digraph
• 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)