Two-sided Cayley graphs

2014/01/13 by Moharram N. Iradmusa, Cheryl E. Praeger, Iradmusa, Moharram N. +1
Biochemistry, Genetics and Molecular Biology · Computer Science · #05C25 #Algorithms and Data Compression #Combinatorics (math.CO) #DNA and Biological Computing #FOS: Mathematics #Genome Rearrangement Algorithms #Group Theory (math.GR)

paper · pdf · doi:10.48550/arxiv.1401.2741

openalex publication_date 2014/01/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We introduce a family of graphs that generalises the class of Cayley graphs. For non-empty subsets L, R of a group G, the two-sided Cayley graph 2SC(G;L,R) is the directed graph with vertex set G and an arc from x to y if and only if y=a^-1xb for some a in L and b in R. Thus, in common with Cayley graphs, two-sided Cayley graphs may be useful to model networks as the same routing and communication scheme can be implemented at each vertex. We determine when two-sided Cayley graphs are simple undirected graphs, and give sufficient conditions for them to be connected, vertex-transitive, or Cayley graphs. Several open problems are posed. Many examples are given, including one on 12 vertices with connected components of sizes 4 and 8.

Citations

• Genome Rearrangements and Sorting by Reversals

Related

• Cayley graphs and symmetric interconnection networks
• Two families of graphs that are Cayley on nonisomorphic groups
• Classification of two-distance-transitive Cayley graphs of the semi-dihedral groups
• A characterization of 2-dimensional Cayley graphs on dihedral groups
• The planar cubic Cayley graphs of connectivity 2