## Publications > Artigos em Revistas Internacionais

### The Commuting Graph of the Symmetric Inverse Semigroup

Araújo, João; Bentz, Wolfram; Janusz Konieczny

Israel Journal of Mathematics, 207 (2014), 103-149
http://arxiv.org/abs/1205.1664

The commuting graph of a finite non-commutative semigroup \$S\$, denoted \$\cg(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 \$\mi(X)\$ be the symmetric inverse semigroup of partial injective transformations on a finite set \$X\$. The semigroup \$\mi(X)\$ has the symmetric group \$\sym(X)\$ of permutations on \$X\$ as its group of units. In 1989, Burns and Goldsmith determined the clique number of the commuting graph of \$\sym(X)\$. In 2008, Iranmanesh and Jafarzadeh found an upper bound of the diameter of \$\cg(\sym(X))\$, and in 2011, Dol\u{z}an and Oblak claimed (but their proof has a GAP) 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 \$\mi(X)\$. We calculate the clique number of \$\cg(\mi(X))\$, the diameters of the commuting graphs of the proper ideals of \$\mi(X)\$, and the diameter of \$\cg(\mi(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 \$\cg(\mi(X))\$ is either 4 or 5. In the process, we obtain several results about semigroups, such as a description of all commutative subsemigroups of \$\mi(X)\$ of maximum order, and analogous results for commutative inverse and commutative nilpotent subsemigroups of \$\mi(X)\$. The paper closes with a number of problems for experts in combinatorics and in group or semigroup theory.