The automorphism group of the reduced complete-empty $X-$join of graphs

Document Type : Research Paper

Authors

Department of Pure Mathematics, Faculty of Mathematical Sciences, University of Kashan, Kashan, Iran

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(\Gamma) &=& \{(x,y) \ | \ x \in V(X) \ \& \ y \in
V(X_x) \},\\ E(\Gamma) &=& \{
(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 said to be reduced if  $x, y \in V(X)$, $x \ne y$ and $N_X(x) \setminus \{ y\} = N_X(y) \setminus \{ x\}$ imply that $(i)$ if $xy \not\in 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. The aim of this paper is 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.

Keywords

References

[1] W. Dorer, Uber die X-Summe von gerichteten Graphen (German), Arch. Math. (Basel), 22 (1971), 24-36.
[2] C. Dubost, L. Oubiena and M. Sagastume, On natural automorphisms of a join of graphs, Rev. Un. Mat. Argentina, 35 (1989), 53-59.
[3] M. Habib and M. C. Maurer, On the X−join decomposition for undirected graphs, Discrete Appl. Math., 1 (1979), 201-207.
[4] R. Hammack, W. Imrich and S. Klavzar, Handbook of Product Graphs, second edition, Discrete Mathematics and its Applications, CRC Press, Boca Raton, FL (2011).
[5] R. L. Hemminger, The group of an X−join of graphs, J. Combin. Theory, 5 (4) (1968), 408-418.
[6] P. Ille, A proof of a conjecture of Sabidussi on graphs idempotent under the lexicographic product, Discrete Math. Vol., 309 (2009), 3518-3522.
[7] G. Sabidussi, Graph Derivatives, Math. Z., 76 (1961), 385-401.
[8] M. Suzuki, Group Theory I, Springer, Berlin (1982).
[9] D. B. West, Introduction to Graph Theory, 2nd ed., Prentice Hall, Upper Saddle River (2001).
Algebraic Structures and Their Applications
Volume 6, Issue 2
November 2019
Pages 21-38

Files

Share

How to cite

Statistics