Cayley digraphs and lexicographic product

Abstract

In this paper, we prove that a Cayley digraph Γ = Cay(G, S) is a nontrivial lexicographical product if and only if there is a nontrivial subgroup H of G such that S∖H is a union of some double cosets of H in G.

Keywords

Cayley graph / lexicoproduct of graphs / double coset

References

[1] Biggs N. Algebraic Graph Theory, 1993 2nd ed. London: Cambridge University Press.

[2] Biggs N., White A. T. Permutation Groups and Combinatorial Structure, 1979, London: Cambridge University Press.

[3] Harary F. On the group of the composition of two graphs. Duke Math J, 1959, 26: 29-34.

[4] Sabidussi G. The composition of graphs. Duke Math J, 1959, 26: 693-696.

[5] Sabidussi G. The lexicographic product of graphs. Duke Math J, 1959, 26: 673-678.