Premium
Two‐sided Group Digraphs and Graphs
Author(s) -
Iradmusa Moharram N.,
Praeger Cheryl E.
Publication year - 2016
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.21901
Subject(s) - combinatorics , mathematics , cayley graph , digraph , valency , vertex (graph theory) , discrete mathematics , vertex transitive graph , chordal graph , strongly connected component , graph , line graph , voltage graph , philosophy , linguistics
We study a family of digraphs (directed graphs) that generalises the class of Cayley digraphs. For nonempty subsets L , R of a group G , we define the two‐sided group digraph2 S ⃗ ( G ; L , R )to have vertex set G , and an arc from x to y if and only if y = ℓ − 1 x r for some ℓ ∈ L and r ∈ R . In common with Cayley graphs and digraphs, two‐sided group digraphs may be useful to model networks as the same routing and communication scheme can be implemented at each vertex. We determine necessary and sufficient conditions on L and R under which2 S ⃗ ( G ; L , R )may be viewed as a simple graph of valency | L | · | R | , and we call such graphs two‐sided group graphs. We also give sufficient conditions for two‐sided group digraphs 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.