The commuting graph of the symmetric inverse semigroup. (English) Zbl 1314.05226

Summary: The commuting graph of a finite non-commutative semigroup \(S\), denoted \(\mathcal{G}(S)\), is a simple graph whose vertices are the non-central elements of \(S\) and two distinct vertices \(x\), \(y\) are adjacent if \(xy=yx\). Let \(\mathcal{I}(X)\) be the symmetric inverse semigroup of partial injective transformations on a finite set \(X\). The semigroup \(\mathcal{I}(X)\) has the symmetric group \(\mathrm{Sym}(X)\) of permutations on \(X\) as its group of units. J. M. Burns and B. Goldsmith [Bull. Lond. Math. Soc. 21, No. 1, 70–72 (1989; Zbl 0632.20003)] determined the clique number of the commuting graph of \(\mathrm{Sym}(X)\). A. Iranmanesh and A. Jafarzadeh [J. Algebra Appl. 7, No. 1, 129–146 (2008; Zbl 1151.20013)] found an upper bound of the diameter of \(G(\mathrm{Sym}(X))\), and D. Dolžan and P. Oblak [Linear Algebra Appl. 435, No. 7, 1657–1665 (2011; Zbl 1231.16037)] claimed that this upper bound is in fact the exact value.
The goal of this paper is to begin the study of the commuting graph of the symmetric inverse semigroup \(\mathcal{I}(X)\).
We calculate the clique number of \(\mathcal{G}(\mathcal{I}(X))\), the diameters of the commuting graphs of the proper ideals of \(\mathcal{I}(X)\), and the diameter of \(\mathcal{G}(\mathcal{I}(X))\) when \(| X|\) is even or a power of an odd prime. We show that when \(| X|\) is odd and divisible by at least two primes, then the diameter of \(\mathcal{G}(\mathcal{I}(X))\) is either 4 or 5. In the process, we obtain several results about semigroups, such as a description of all commutative subsemigroups of \(\mathcal{I}(X)\) of maximum order, and analogous results for commutative inverse and commutative nilpotent subsemigroups of \(\mathcal{I}(X)\). The paper closes with a number of problems for experts in combinatorics and in group or semigroup theory.


05E15 Combinatorial aspects of groups and algebras (MSC2010)
05C12 Distance in graphs
20B30 Symmetric groups
20M20 Semigroups of transformations, relations, partitions, etc.
20M14 Commutative semigroups
20B35 Subgroups of symmetric groups
16Y60 Semirings


Full Text: DOI arXiv


[1] A. Abdollahi, S. Akbari and H. R. Maimani, Non-commuting graph of a group, Journal of Algebra 298 (2006), 468-492. · Zbl 1105.20016
[2] J. M. André, J. Araújo and J. Konieczny, Regular centralizers of idempotent transformations, Semigroup Forum 82 (2011), 307-318. · Zbl 1227.20054
[3] J. M. André, V. H. Fernandes and J. D. Mitchell, Largest 2-generated subsemigroups of the symmetric inverse semigroup, Proceedings of the Edinburgh Mathematical Society 50 (2007), 551-561. · Zbl 1148.20045
[4] J. Araújo and J. Konieczny, Automorphism groups of centralizers of idempotents, Journal of Algebra 269 (2003), 227-239. · Zbl 1037.20062
[5] J. Araújo and J. Konieczny, Semigroups of transformations preserving an equivalence relation and a cross-section, Communications in Algebra 32 (2004), 1917-1935. · Zbl 1068.20061
[6] J. Araújo, M. Kinyon and J. Konieczny, Minimal paths in the commuting graphs of semigroups, European Journal of Combinatorics 32 (2011), 178-197. · Zbl 1227.05161
[7] J. Araújo and J. Konieczny, A method for finding new sets of axioms for classes of semigroups, Archive for Mathematical Logic 51 (2012), 461-474. · Zbl 1262.20059
[8] C. Bates, D. Bundy, S. Perkins and P. Rowley, Commuting involution graphs for symmetric groups, Journal of Algebra 266 (2003), 133-153. · Zbl 1034.20003
[9] E. A. Bertram, Some applications of graph theory to finite groups, Discrete Mathematics 44 (1983), 31-43. · Zbl 0506.05060
[10] D. Bundy, The connectivity of commuting graphs, Journal of Combinatorial Theory. Series A 113 (2006), 995-1007. · Zbl 1098.05046
[11] J. M. Burns and B. Goldsmith, Maximal order abelian subgroups of symmetric groups, Bulletin of the London Mathematical Society 21 (1989), 70-72. · Zbl 0632.20003
[12] M. R. Darafsheh, Groups with the same non-commuting graph, Discrete Applied Mathematics 157 (2009), 833-837. · Zbl 1184.20023
[13] D. Dolžan and P. Oblak, Commuting graphs of matrices over semirings, Linear Algebra and its Applications 435 (2011), 1657-1665. · Zbl 1231.16037
[14] Fernandes, V. H., Presentations for some monoids of partial transformations on a finite chain: a survey, 363-378 (2002), River Edge, NJ · Zbl 1030.20042
[15] A. G. Ganyushkin and T. V. Kormysheva, On nilpotent subsemigroups of a finite symmetric inverse semigroup, Matematicheskie Zametki 56 (1994), 29-35, 157 (Russian); translation in Mathematical Notes 56 (1994), 896-899 (1995). · Zbl 0837.20075
[16] O. Ganyushkin and V. Mazorchuk, Classical Finite Transformation Semigroups. An Introduction, Algebra and Applications, Vol. 9, Springer-Verlag, London, 2009. · Zbl 1166.20056
[17] The GAP Group, GAP—Groups, Algorithms, and Programming, Version 4.4.12, 2008, http://www.gap-system.org.
[18] M. Giudici and C. Parker, There is no upper bound for the diameter of the commuting graph of a finite group, Journal of Combinatorial Theory. Series A 120 (2013), 1600-1603. · Zbl 1314.05055
[19] J. M. Howie, Fundamentals of Semigroup Theory, Oxford University Press, New York, 1995. · Zbl 0835.20077
[20] A. Iranmanesh and A. Jafarzadeh, On the commuting graph associated with the symmetric and alternating groups, Journal of Algebra and its Applications 7 (2008), 129-146. · Zbl 1151.20013
[21] J. Konieczny, Green’s relations and regularity in centralizers of permutations, Glasgow Mathematical Journal 41 (1999), 45-57. · Zbl 0924.20049
[22] J. Konieczny, Semigroups of transformations commuting with idempotents, Algebra Colloquium 9 (2002), 121-134. · Zbl 1005.20046
[23] J. Konieczny, Semigroups of transformations commuting with injective nilpotents, Mathematica Bohemica 128 (2003), 179-186. · Zbl 1027.20046
[24] J. Konieczny, Regular, inverse, and completely regular centralizers of permutations, Communications in Algebra 32 (2004), 1551-1569. · Zbl 1068.20065
[25] J. Konieczny, Centralizers in the semigroup of injective transformations on an infinite set, Bulletin of the Australian Mathematical Society 82 (2010), 305-321. · Zbl 1205.20063
[26] J. Konieczny and S. Lipscomb, Centralizers in the semigroup of partial transformations, Mathematica Japonica 48 (1998), 367-376. · Zbl 0917.20051
[27] L. G. Kovács and C. E. Praeger, Finite permutation groups with large abelian quotients, Pacific Journal of Mathematics 136 (1989), 283-292. · Zbl 0679.20002
[28] M. V. Lawson, Inverse Semigroups. The Theory of Partial Symmetries, World Scientific Publishing, River Edge, NJ, 1998. · Zbl 1079.20505
[29] S. Lipscomb, Symmetric Inverse Semigroups, Mathematical Surveys and Monographs, Vol. 46, American Mathematical Society, Providence, RI, 1996. · Zbl 0857.20047
[30] B. H. Neumann, A problem of Paul Erdős on groups, Australian Mathematical Society. Journal. Series A. Pure Mathematicas and Statistics 21 (1976), 467-472. · Zbl 0333.05110
[31] A. L. T. Paterson, Groupoids, Inverse Semigroups, and their Operator Algebras, Progress in Mathematics, Vol. 170, Birkhäuser Boston, Boston, MA, 1999. · Zbl 0913.22001
[32] M. Petrich, Inverse Semigroups, John Wiley & Sons, New York, 1984. · Zbl 0546.20053
[33] A. S. Rapinchuk and Y. Segev, Valuation-like maps and the congruence subgroup property, Inventiones Mathematicae 144 (2001), 571-607. · Zbl 0999.16016
[34] A. S. Rapinchuk, Y. Segev and G. M. Seitz, Finite quotients of the multiplicative group of a finite dimensional division algebra are solvable, Journal of the American Mathematical Society 15 (2002), 929-978. · Zbl 1008.16018
[35] Y. Segev, The commuting graph of minimal nonsolvable groups, Geometriae Dedicata 88 (2001), 55-66. · Zbl 0994.20012
[36] L. H. Soicher, The GRAPE package for GAP, Version 4.3, 2006, http://www.maths.qmul.ac.uk/ leonard/grape/. · Zbl 1148.20045
[37] H. Wielandt, Finite Permutation Groups, Academic Press, New York, 1964. · Zbl 0138.02501
[38] X. Yang, A classification of maximal inverse subsemigroups of the finite symmetric inverse semigroups, Communications in Algebra 27 (1999), 4089-4096. · Zbl 0943.20064
[39] X. Yang, Extensions of Clifford subsemigroups of the finite symmetric inverse semigroup, Communications in Algebra 33 (2005), 381-391. · Zbl 1071.20057
[40] L. Zhang and W. Shi, Recognition of the projective general linear group PGL(2, q) by its noncommuting graph, Journal of Algebra and its Applications 10 (2011), 201-218. · Zbl 1231.20017
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.