Tadayyonfar, A., Ashrafi, A. (2019). The automorphism group of the reduced complete-empty $X-$join of graphs. Algebraic Structures and Their Applications, 6(2), 21-38. doi: 10.29252/as.2019.1428

Adel Tadayyonfar; Ali Reza Ashrafi. "The automorphism group of the reduced complete-empty $X-$join of graphs". Algebraic Structures and Their Applications, 6, 2, 2019, 21-38. doi: 10.29252/as.2019.1428

Tadayyonfar, A., Ashrafi, A. (2019). 'The automorphism group of the reduced complete-empty $X-$join of graphs', Algebraic Structures and Their Applications, 6(2), pp. 21-38. doi: 10.29252/as.2019.1428

Tadayyonfar, A., Ashrafi, A. The automorphism group of the reduced complete-empty $X-$join of graphs. Algebraic Structures and Their Applications, 2019; 6(2): 21-38. doi: 10.29252/as.2019.1428

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

^{}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.

[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).