{{primary sources|date=November 2025}} In mathematics, the '''commuting graph''' of a semigroup, or in particular of a group, is an undirected graph in which the vertices are elements of the semigroup and there is an edge between any pair of elements that commute (that is, there is an edge between vertices {{math|''x''}} and {{math|''y''}} if and only if {{math|1=''xy''=''yx''}} in the semigroup). Commuting graphs have been used to study groups and semigroups by seeking relationships between the combinatorial structure of the graph and the algebraic structure of the group or semigroup.
Depending on the author, the vertex set may comprise every element of the semigroup, or only the non-central elements (since the central elements — those elements of a semigroup that commute with every other element — would always form a complete subgraph, every vertex of which would be adjacent to every vertex of the whole commuting graph). If the central elements are excluded, the commuting graph is usually only defined for non-abelian groups and non-commutative semigroups (since in these cases the commuting graph would be empty).
For the purposes of this article, the vertices of the commuting graph are the ''non-central'' elements unless otherwise noted.
==History==
The concept of a commuting graph was first introduced for groups in 1955,<ref>{{cite journal |last1=Brauer |first1=Richard |author-link=Richard Brauer |last2=Fowler |first2=K. A. |title=On Groups of Even Order |journal=The Annals of Mathematics |date=November 1955 |volume=62 |issue=3 |page=565 |doi=10.2307/1970080 |jstor=1970080 }}</ref> although the term 'commuting graph' was not coined until 1983.<ref>{{cite journal |last1=Bertram |first1=Edward A. |title=Some applications of graph theory to finite groups |journal=Discrete Mathematics |date=1983 |volume=44 |issue=1 |pages=31–43 |doi=10.1016/0012-365X(83)90004-3}}</ref> They played a implicit role in Bernd Fischer's discovery of the sporadic groups now known as the Fischer groups.<ref>{{cite journal |last1=Fischer |first1=Bernd |title=Finite groups generated by 3-transpositions. I |journal=Inventiones Mathematicae |date=September 1971 |volume=13 |issue=3 |pages=232–246 |doi=10.1007/BF01404633 |bibcode=1971InMat..13..232F }}</ref>
The study of the commuting graphs of semigroups other than groups was initiated in 2011.<ref>{{cite journal |last1=Araújo |first1=João |last2=Kinyon |first2=Michael |last3=Konieczny |first3=Janusz |title=Minimal paths in the commuting graphs of semigroups |journal=European Journal of Combinatorics |date=February 2011 |volume=32 |issue=2 |pages=178–197 |doi=10.1016/j.ejc.2010.09.004}}</ref>
==Properties==
===Connectedness and diameters===
It is possible for a commuting graph to be non-connected and thus not to have a finite diameter.
For a finite set <math>X</math>, the commuting graph of the symmetric group <math>\mathcal{S}(X)</math> is connected if and only if <math>|X|</math> and <math>|X|-1</math> are non-prime, and the commuting graph of the alternating group <math>\mathcal{A}(X)</math> is connected if and only if <math>|X|</math>, <math>|X|-1</math>, and <math>|X|-2</math> are non-prime. When connected, the commuting graphs of <math>\mathcal{S}(X)</math> and <math>\mathcal{A}(X)</math> have diameter at most 5.<ref>{{cite journal |last1=Iranmanesh |first1=A. |last2=Jafarzadeh |first2=A. |title=On the commuting graph associtated with the symmetric and alternating groups |journal=Journal of Algebra and Its Applications |date=February 2008 |volume=07 |issue=1 |pages=129–146 |doi=10.1142/S0219498808002710}}</ref>
The commuting graph of the symmetric inverse semigroup <math>\mathcal{I}(X)</math> is not connected if and only if <math>|X|</math> is an odd prime. When <math>|X|</math> is not an odd prime, it has diameter 4 or 5, and is known to have diameter 4 when <math>|X|</math> is even and diameter 5 when <math>|X|</math> is a power of an odd prime.<ref>{{cite journal |last1=Araújo |first1=João |last2=Bentz |first2=Wolfram |last3=Janusz |first3=Konieczny |title=The commuting graph of the symmetric inverse semigroup |journal=Israel Journal of Mathematics |date=April 2015 |volume=207 |issue=1 |pages=103–149 |doi=10.1007/s11856-015-1173-9 |url=https://hull-repository.worktribe.com/output/900703 |hdl=10400.2/3813 |hdl-access=free }}</ref>
For every natural number {{math|''n''}}, there is a finite group whose commuting graph is connected and has diameter equal to {{math|''n''}}.<ref>{{cite journal |last1=Cutolo |first1=Giovanni |title=On a construction by Giudici and Parker on commuting graphs of groups |journal=Journal of Combinatorial Theory, Series A |date=1 November 2022 |volume=192 |article-number=105666 |doi=10.1016/j.jcta.2022.105666}}</ref> But if a finite group has trivial center and its commuting graph is connected, then its diameter is at most 10.<ref>{{cite journal |last1=Morgan |first1=G.L. |last2=Parker |first2=C.W. |title=The diameter of the commuting graph of a finite group with trivial centre |journal=Journal of Algebra |date=November 2013 |volume=393 |pages=41–59 |doi=10.1016/j.jalgebra.2013.06.031}}</ref>
The commuting graph of a completely simple semigroup is never connected except when it is a group, and if it not a group, its connected components are the commuting graphs including central elements of its maximal subgroups<ref>{{cite journal |last1=Paulista |first1=Tânia |title=Commuting graphs of completely simple semigroups |journal=Communications in Algebra |date=3 October 2025 |volume=53 |issue=10 |pages=4215–4226 |doi=10.1080/00927872.2025.2481079|doi-access=free }}</ref> (which, by the Rees–Suschkewitsch theorem, are isomorphic<ref>{{cite book |last1=Howie |first1=John M. |author-link=John Mackintosh Howie |title=Fundamentals of Semigroup Theory |date=1995 |publisher=Clarendon Press |location=Oxford |isbn=0-19-851194-9 |page=77}}</ref>).
===Simple groups===
Non-abelian finite simple groups are uniquely characterized by their commuting graphs, in the sense that if {{math|''G''}} is a non-abelian finite simple group and {{math|''H''}} is a group, and the commuting graphs of {{math|''G''}} and the commuting graph of {{math|''H''}} are isomorphic (as graphs), then {{math|''G''}} and {{math|''H''}} are isomorphic (as groups). This result was conjectured in 2006<ref>{{cite journal |last1=Abdollahi |first1=A. |last2=Akbari |first2=S. |last3=Maimani |first3=H.R. |title=Non-commuting graph of a group |journal=Journal of Algebra |date=April 2006 |volume=298 |issue=2 |pages=468–492 |doi=10.1016/j.jalgebra.2006.02.015}}</ref> and proved by different authors for sporadic groups,<ref>{{cite journal |last1=Han |first1=Zhangjia |last2=Chen |first2=Guiyun |last3=Guo |first3=Xiuyun |title=A characterization theorem for sporadic simple groups |journal=Siberian Mathematical Journal |date=November 2008 |volume=49 |issue=6 |pages=1138–1146 |doi=10.1007/s11202-008-0111-z |bibcode=2008SibMJ..49.1138H }}</ref> alternating groups,<ref>{{cite journal |last1=Abdollahi |first1=Alireza |last2=Shahverdi |first2=Hamid |title=Characterization of the alternating group by its non-commuting graph |journal=Journal of Algebra |date=May 2012 |volume=357 |pages=203–207 |doi=10.1016/j.jalgebra.2012.01.038}}</ref> and groups of Lie type.<ref>{{cite journal |last1=Solomon |first1=Ronald M. |last2=Woldar |first2=Andrew J. |title=Simple groups are characterized by their non-commuting graphs |journal=Journal of Group Theory |date=1 November 2013 |volume=16 |issue=6 |pages=793–824 |doi=10.1515/jgt-2013-0021}}</ref>
==Notes==
{{reflist|2}}
Category:Application-specific graphs Category:Group theory Category:Semigroup theory