Document Type : Review Paper


1 Department of Pure Mathematics, Ferdowsi University of Mashhad, P.O. Box 1159, Mashhad 91775, Iran.

2 Department of Pure Mathematics and Center of Excellence in Analysis on Algebraic Structures, Ferdowsi University of Mashhad, Mashhad, Iran.


To a simple graph $G=(V,E)$, we correspond a simple graph $G_{\triangle,\square}$ whose vertex set is $\{\{x,y\}: x,y\in V\}$ and two vertices $\{x,y\},\{z,w\}\in G_{\triangle,\square}$ are adjacent if and only if $\{x,z\},\{x,w\},\{y,z\},\{y,w\}\in V\cup E$. The graph $G_{\triangle,\square}$ is called the $(\triangle,\square)$-edge graph of the graph $G$. In this paper, our ultimate goal is to provide a link between the connectedness of $G$ and $G_{\triangle,\square}$.


1. A. Abdollahi, S. Akbari and H. R. Maimani, Non-commuting graph of a group, J. Algebra, 298 (2006), 468–492
2. S. Akbari, A. Mohammedian, H. Radjavi and P. Raja, On diameters of commuting graphs,Linear Algebra Appl., 418 (2006), 161–176.
3. R. Barzgar, A. Erfanian and M. Farrokhi, Probability of mutually commuting two finite subsets of a finite group, Ars. Combinatoria, 124 (2016), 165–176.
4. C. Bates, D. Bundy, S. Hart and P. Rowley, A note on commuting graphs for symmetric groups, Electron. J. Combin., 16 (2009), 1–13.
5. J. A. Bondy and J. S. R. Murty, Graph theory with applications, Elsevier, 1977.
6. A. Erfanian, B. Tolue and N. H. Sarmin, Some considerations on the n-th commutativity degree of finite groups, Ars. Combinatoria, 122 (2015), 257–267.
7. A. Erfanian, R. Rezaei, and P. Lescot, On the relative commutativity degree of a subgroup of a finite group, Comm. Algebra, 35 (2007), 4183–4198
8. C. Godsil and G. Royle, Algebraic graph theory, Springer, 2001.
9. A. Iranmanesh and A. Jafarzadeh, Characterization of finite groups by their commuting graph, Acta Math. Acad. Paedagog. Nyhazi.(N.S), 23 (2007), 1–13.
10. A. R. Moghaddamfar, W. J. Shi, W. Zhou and A. R. Zokayi, On the noncommuting graph associated with a finite group, Siberian Math. J., 46 (2005),
11. D. B. West, Introduction to group theory, Second edition, Prentice Hall. Inc., 2001.