Frobenius circulant graphs of valency six, Eisenstein-Jacobi networks, and hexagonal meshes

DOI10.1016/J.EJC.2013.11.004MaRDI QIDQ2637237zbMATH OpenOpenAlexFDO

Authors Alison Thomson, Sanming Zhou

Publication date 10 February 2014

Published in European Journal of Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

Cayley graphEisenstein-Jacobi graph

Mathematics Subject Classification ID

Graphs and abstract algebra (groups, rings, fields, etc.) (05C25)

Abstract: A Frobenius group is a transitive but not regular permutation group such that only the identity element can fix two points. A finite Frobenius group can be expressed as $G=KtimesH$ with $K$ a nilpotent normal subgroup. A first-kind $G$-Frobenius graph is a Cayley graph on $K$ with connection set $S$ an $H$-orbit on $K$ generating $K$, where $H$ is of even order or $S$ consists of involutions. We classify all 6-valent first-kind Frobenius circulant graphs such that the underlying kernel $K$ is cyclic. We give optimal gossiping and routing algorithms for such a circulant and compute its forwarding indices, Wiener indices and minimum gossip time. We also prove that its broadcasting time is equal to its diameter plus two or three. We prove that all 6-valent first-kind Frobenius circulants with cyclic kernels are Eisenstein-Jacobi graphs, the latter being Cayley graphs on quotient rings of the ring of Eisenstein-Jacobi integers. We also prove that larger Eisenstein-Jacobi graphs can be constructed from smaller ones as topological covers, and a similar result holds for 6-valent first-kind Frobenius circulants. As a corollary any Eisenstein-Jacobi graph with order congruent to 1 modulo 6 and underlying Eisenstein-Jacobi integer not an associate of a real integer, is a cover of a 6-valent first-kind Frobenius circulant. A distributed real-time computing architecture known as HARTS or hexagonal mesh is a special 6-valent first-kind Frobenius circulant.

Recommendations

• FROBENIUS CIRCULANT GRAPHS OF VALENCY FOUR
• On 4-valent Frobenius circulant graphs
• Rotational circulant graphs
• Gossiping and routing in second-kind Frobenius graphs
• On the edge-forwarding indices of Frobenius graphs

Cites work

• A Class of Arc-Transitive Cayley Graphs as Models for Interconnection Networks
• A group-theoretic model for symmetric interconnection networks
• A survey on Knödel graphs.
• A survey on multi-loop networks.
• Circulants and the chromatic index of Steiner triple systems
• Complete rotations in Cayley graphs
• Finding optimal routings in Hamming graphs
• FROBENIUS CIRCULANT GRAPHS OF VALENCY FOUR
• Gossiping and routing in second-kind Frobenius graphs
• Gossiping and routing in undirected triple-loop networks
• Group Action Graphs and Parallel Architectures
• Hamiltonian cycles and paths in Cayley graphs and digraphs---a survey
• scientific article; zbMATH DE number 4004216 (Why is no real title available?)
• scientific article; zbMATH DE number 3756556 (Why is no real title available?)
• scientific article; zbMATH DE number 1054728 (Why is no real title available?)
• scientific article; zbMATH DE number 857072 (Why is no real title available?)
• scientific article; zbMATH DE number 894528 (Why is no real title available?)
• Isomorphic Cayley graphs on nonisomorphic groups
• Modeling Toroidal Networks with the Gaussian Integers
• Network properties of double and triple fixed step graphs
• New methods for using Cayley graphs in interconnection networks
• On 4-valent Frobenius circulant graphs
• On forwarding indices of networks
• On isomorphisms of connected Cayley graphs
• On orbital regular graphs and Frobenius graphs
• Perfect Codes for Metrics Induced by Circulant Graphs
• Performance analysis of virtual cut-through switching in HARTS: a hexagonal mesh multicomputer
• 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 edge-forwarding index or orbital regular graphs
• The Lattice Point Covering Theorem for Rectangles
• Wiener index of hexagonal systems

Cited in

(11)

• Cyclotomic graphs and perfect codes
• Cube-connected circulants: bisection width, Wiener and forwarding indices
• A family of efficient six-regular circulants representable as a Kronecker product
• Gossiping and routing in second-kind Frobenius graphs
• Resolvable Mendelsohn designs and finite Frobenius groups
• Tree connectivities of Cayley graphs on abelian groups with small degrees
• Recursive cubes of rings as models for interconnection networks
• FROBENIUS CIRCULANT GRAPHS OF VALENCY FOUR
• On 4-valent Frobenius circulant graphs
• Rotational circulant graphs
• Forwarding and optical indices of 4-regular circulant networks

This page was built for publication: Frobenius circulant graphs of valency six, Eisenstein-Jacobi networks, and hexagonal meshes

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