The Automorphism Group of the Reduced Complete-Empty $X-$Join of Graphs

Abstract

Suppose $X$ is a simple graph. The $X-$join $\Gamma$ of a set of complete or empty graphs $\{X_x{\}}_{x\in V(X)}$ is a simple graph with the following vertex and edge sets: \begin{eqnarray*} V(Γ) &=& \{(x,y) \ | \ x \in V(X) \ \& \ y \in V(X_x) \},\\ E(Γ) &=& \{(x,y)(x^\prime,y^\prime) \ | \ xx^\prime \in E(X) \ or \ else \ x = x^\prime \ \& \ yy^\prime \in E(X_x)\}. \end{eqnarray*} The $X-$join graph $\Gamma$ is called reduced if for vertices $x,y\in V(X)$, $x\ne y$, $N_X(x)\setminus \{y\}=N_X(y)\setminus \{x\}$ implies that $(i)$ if $xy\notin E(X)$ then the graphs $X_x$ or $X_y$ are non-empty; $(ii)$ if $xy\in E(X)$ then $X_x$ or $X_y$ are not complete graphs. In this paper, we want to explore how the graph theoretical properties of $X-$join of graphs effect on its automorphism group. Among other results we compute the automorphism group of reduced complete-empty $X-$join of graphs.

arXiv comment19 pages, 0 figure