The graph lexicographic (or lexicographical) product is the graph product denoted 
and defined by the adjacency relations (
) or (
and 
). The graph lexicographic product is also known as the
graph composition (Harary 1994, p. 21).
For finite graphs 
and 
with nonempty vertex sets, independently
applying a graph automorphism of 
in each copy of 
and permuting the copies according to a graph
automorphism of 
always gives a subgroup of 
.
A theorem due to Sabidussi (1959, 1961) states that this subgroup
is all of 
iff 
is connected whenever two
distinct vertices of 
have the same open graph
neighborhood, and the graph complement 
is connected whenever two distinct vertices of
have the same closed neighborhood (see also
Grech and Kisielewicz 2022). Equivalently, under exactly these conditions, the automorphism group is the semidirect
product
![Aut(G-H)=Aut(H)^(|V(G)|)×AdjustmentBox[│, BoxMargins -> {{-0.27, 0.13913}, {-0.5, 0.5}}]Aut(G).](/images/equations/GraphLexicographicProduct/NumberedEquation1.svg) |
Here 
acts on the 
factors of 
by permuting them according to its natural group action
on 
.
For a positive integer 
, the product 
with the empty graph 
is the uniform 
-fold graph blow-up of 
.
For 
,
writing 
for the symmetric group on 
letters, the theorem specializes to
![Aut(G-K^__t)=S_t^(|V(G)|)×AdjustmentBox[│, BoxMargins -> {{-0.27, 0.13913}, {-0.5, 0.5}}]Aut(G)](/images/equations/GraphLexicographicProduct/NumberedEquation2.svg) |
iff 
has no false twins, i.e., no
two distinct vertices with the same open graph
neighborhood. In this case, the group order is
.
Graph lexicographic products can be computed in the Wolfram Language using GraphProduct[G1, G2, "Lexicographical"].
The "double graph" of a given graph 
is the graph lexicographic product 
.
