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 Γ of a set of
complete or empty graphs {Xx}x∈V(X) is a simple graph with the following vertex and edge sets:
V(Γ)={(x,y) | x∈V(X) & y∈V(Xx)},E(Γ)={(x,y)(x′,y′) | xx′∈E(X) or else x=x′ & yy′∈E(Xx)}.
The X−join graph Γ is said to be reduced if  x,y∈V(X), x≠y and NX(x)∖{y}=NX(y)∖{x} imply that (i) if xy∉E(X) then the graphs Xx or Xy are non-empty; (ii) if xy∈E(X) then Xx or Xy 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