The group of an X-join of graphs (Q5576808)

The vertex set of a graph \(X\) (without self-loops and multiple edges) is denoted by \(V(X)\). Let a graph \(Y_x\) be assigned to any \(x\) \((\in V(X))\), let a graph \(Z\) with all the pairs \((x,y)\) satisfying \(y\in V_x\), \(x\in X\), as vertices, be formed in such a manner that two vertices of \(Z\) are adjacent of either their first components are adjacent or the first components coincide and the second ones are adjacent. This graph \(Z\) is called the \(X\)-join of the \(Y_x\)'s. To an automorphism \(\mu\) of \(X\) fulfilling \(Y_x\cong Y_{\mu(x)}\) and to automorphisms of each \(Y_x\); one can construct an automorphism of \(Z\) in a natural way. Some necessary and sufficient conditions are established in order that every automorphism of \(Z\) should be obtainable in the natural manner. The particular case of the \(X\)-join when all the \(Y_x\)'s are isomorphic to \(Y\) is called the lexicographic product of \(X\) and \(Y\). Instead of an incorrect theorem published in a former article [Duke Math. J. 33, 499--501 (1966; Zbl 0144.23201)] a criterion is given for the automorphism group of the lexicographic product of two graphs \(X\), \(Y\) to be the wreath product of the automorphism groups of \(X\) and \(Y\). In the mentioned conditions the following notion is extensively used: a subset \(A\) of \(V(X)\) is externally related if the adjacency of \(a\) and \(c\) implies the adjacency of \(b\) and \(c\) whenever \(a\in A\), \(b\in A\), \(c\in V(X) - A\). Finally, a criterion is stated for a permutation group to be permutationally isomorphic to the automorphism group of a suitable graph.