On the Semigroup Whose Elements Are Subgraphs of a Complete Graph

Abstract

Let $K_n$ be a complete graph on n vertices. Denote by $S{K}_n$ the set of all subgraphs of $K_n$. For each $G,H\in S{K}_n$, the ring sum of G and H is a graph whose vertex set is $V\left(G\right)\cup V\left(H\right)$ and whose edges are that of either G or H, but not of both. Then $S{K}_n$ is a semigroup under the ring sum. In this paper, we study Green’s relations on $S{K}_n$ and characterize ideals, minimal ideals, maximal ideals, and principal ideals of $S{K}_n$. Moreover, maximal subsemigroups and a class of maximal congruences are investigated. Furthermore, we prescribe the natural order on $S{K}_n$ and consider minimal elements, maximal elements and covering elements of $S{K}_n$ under this order.

1. Introduction and Preliminaries

One of several ways to study the algebraic structures in mathematics is to consider the relations between graph theory and semigroup theory known as algebraic graph theory. It is a branch of mathematics concerning the study of graphs in connection to semigroup theory in which algebraic methods are applied to problems about graphs. Cayley graphs of semigroups are special graphs such that many authors have widely studied, see for examples [1,2,3]. Studying on characterization of those graphs is a way of considering the relations between graphs and semigroups in the sense that such graphs are constructed from semigroups. On the other hand, the construction of a semigroup from a given graph is also interesting to study. However, there are no authors considering the properties of semigroups which are constructed from graphs. Certain special types of connected graphs are also interesting to study and look for some applications, especially a complete graph which is a graph in which every two distinct vertices are adjacent. Some authors considered a complete graph for applying its structure to complete their research, see for examples [4,5]. Furthermore, an algebraic formation on connected graphs has been studied in the sense of defining some binary operations among a pair of such graphs. Several authors investigated some properties of families of graphs together which graph operations, see for examples [6,7,8].

In this paper, we consequently construct a new semigroup from a complete graph and study some valuable properties of such a semigroup. We need to consider that all sets mentioned in this paper are assumed to be finite sets. Some basic preliminaries, useful notations, and valuable mathematical terminologies needed in what follows are prescribed. Note that a graph G is an order pair $\left(V\right(G),E(G\left)\right)$ of a nonempty vertex set $V\left(G\right)$ and an edge set $E\left(G\right)$. For all undefined notions and notations, we refer the reader to [9,10].

Now, we give the description of the semigroup focused in this paper. Let $K_n$ be a complete graph on n vertices and $S{K}_n$ the set of all subgraphs of $K_n$. For each $G,H\in S{K}_n$, the $\mathit{ring}\mathit{sum}$ $G\oplus H$ of G and H is a graph whose vertex set $V(G\oplus H)=V\left(G\right)\cup V\left(H\right)$ and whose edges are that of either G or H, but not of both, that is, $E(G\oplus H)=\left[E\right(G)\cup E(H\left)\right]\backslash \left[E\right(G)\cap E(H\left)\right]$. It is easy to verify that $(S{K}_n,\oplus )$ is a commutative semigroup. For convenience, we write $GH$ instead of $G\oplus H$.

Throughout this paper, we shall denote the set of n vertices of $K_n$ by the set $X_n=\{v_1,v_2,\dots ,v_n\}$. For each a nonempty subset A of $X_n$, denote by ${\varphi }_A$ a graph with a vertex set $V\left({\varphi }_A\right)=A$ and $E\left({\varphi }_A\right)=\varnothing$ which is called an $\mathit{empty}\mathit{graph}$. For convenience, if $A=\left\{v\right\}$, then we write ${\varphi }_v$ instead of ${\varphi }_{\left\{v\right\}}$. We obviously obtain that $G^2={\varphi }_{V\left(G\right)}$ and $G{\varphi }_A=G$ for every $G\in S{K}_n$ and $A\subseteq V\left(G\right)$.

In this section, we consider the regularity and Green’s relations on the semigroup $S{K}_n$. Moreover, we also determine the rank of $S{K}_n$.

Proposition 1.

$S{K}_n$ is a regular semigroup.

Proof. 

Let G be an element of $S{K}_n$. We will show that $G^3=G$. It is obvious that $V\left(G^3\right)=V\left(G\right)$. Consider

$$\begin{array}{cc}\hfill E\left(G^3\right)& =E\left(G^{2}G\right)\hfill \\ & =[E\left(G^2\right)\cup E\left(G\right)]\backslash [E\left(G^2\right)\cap E\left(G\right)]\hfill \\ & =[\varnothing \cup E(G\left)\right]\backslash [\varnothing \cap E(G\left)\right]\hfill \\ & =E\left(G\right),\hfill \end{array}$$

we conclude that $G^3=G$ which implies that G is regular. ☐

Moreover, we observe that the set of all empty graphs in $S{K}_n$ forms the set of all idempotents of $S{K}_n$, denoted by $\mathcal{E}\left(S{K}_n\right)$, that is,

$$\mathcal{E}\left(S{K}_n\right)=\{{\varphi }_A\in S{K}_n:\varnothing \ne A\subseteq X_n\}.$$

Clearly, $|\mathcal{E}\left(S{K}_n\right)|=2^n-1$. Furthermore, since $S{K}_n$ is regular and its idempotents commute, it follows from Theorem 5.1.1 [9] (p. 145) that $S{K}_n$ is an inverse semigroup.

Next, we will describe Green’s relations on $S{K}_n$.

Proposition 2.

Let $G,H\in S{K}_n$. Then $G=KH$ for some $K\in S{K}_n$ if and only if $V\left(H\right)\subseteq V\left(G\right)$. Consequently, $G\mathcal{L}H$ if and only if $V\left(G\right)=V\left(H\right)$.

Proof. 

Assume that $G=KH$ for some $K\in S{K}_n$. Then $V\left(G\right)=V\left(KH\right)=V\left(K\right)\cup V\left(H\right)$. Hence $V\left(H\right)\subseteq V\left(G\right)$. Conversely, assume that $V\left(H\right)\subseteq V\left(G\right)$. Define K to be the graph with the vertex set $V\left(K\right)=V\left(G\right)$ and the edge set $E\left(K\right)=\left[E\right(G)\backslash E(H\left)\right]\cup \left[E\right(H)\backslash E(G\left)\right]$. We will show that $G=KH$. It is easy to see that $V\left(KH\right)=V\left(K\right)\cup V\left(H\right)=V\left(G\right)\cup V\left(H\right)=V\left(G\right)$ and

$$\begin{array}{cc}\hfill E\left(KH\right)& =\left[E\right(K)\cup E(H\left)\right]\backslash \left[E\right(K)\cap E(H\left)\right]\hfill \\ & =\left[E\right(G)\cup E(H\left)\right]\backslash \left[E\right(H)\backslash E(G\left)\right]\hfill \\ & =E\left(G\right).\hfill \end{array}$$

Therefore, $G=KH$. ☐

Furthermore, we can directly obtain that $\mathcal{L}=\mathcal{R}=\mathcal{H}=\mathcal{D}=\mathcal{J}$ since $S{K}_n$ is commutative.

Given a nonempty subset A of a semigroup S, denote by $\langle A\rangle$ the subsemigroup of S generated by A. The rank of S, denoted by rank(S), is the minimum cardinality of a generating set for a semigroup S.

In order to consider the rank of $S{K}_n$, we shall denote by $H\left[e\right]$ an induced subgraph of H induced by e where $e\in E\left(H\right)$. Let $T_{ij}$ denote a graph in $S{K}_n$ with $V\left(T_{ij}\right)=\{v_i,v_j\}$ where $i\ne j$ and $E\left(T_{ij}\right)=\left\{v_i{v}_j\right\}$.

Theorem 1.

rank($S{K}_n$) = $\left(\begin{array}{c}n\\ 2\end{array}\right)+n$.

Proof. 

Let $\mathcal{M}=\{T_{ij}:i\ne j\}$ and $\mathcal{N}=\{{\varphi }_v:v\in X_n\}$. We claim that every element of $S{K}_n$ can be generated by some elements of $\mathcal{M}\cup \mathcal{N}$. Let $T\in S{K}_n$. If T contains isolated vertices, then those isolated vertices can be generated by corresponding elements in $\mathcal{N}$. So we now consider in the case where T has no isolated vertices. It is not difficult to verify that the set of all subgraphs $T\left[e\right]$ where $e\in E\left(T\right)$ is a subset of $\mathcal{M}$ and $T=\underset{e\in E\left(T\right)}{\oplus }T\left[e\right]$. This means that T can be written as a product of some elements of $\mathcal{M}$ under the operation ⊕. Hence $\mathcal{M}\cup \mathcal{N}$ is a generating set of $S{K}_n$ which implies that

$$\mathrm{rank}\left(S{K}_n\right)\le |\mathcal{M}\cup \mathcal{N}|=\left(\begin{array}{c}n\\ 2\end{array}\right)+n$$

Moreover, we can easily observe that both of $H\in \mathcal{N}$ and $G\in \mathcal{M}$ cannot be written as a product of other elements in $S{K}_n$. Therefore, all elements in $\mathcal{M}\cup \mathcal{N}$ must belong to every generating set of $S{K}_n$. Consequently,

$$\mathrm{rank}\left(S{K}_n\right)=\left(\begin{array}{c}n\\ 2\end{array}\right)+n.\hspace{1em}☐$$

2. Ideals of ${\mathit{SK}}_{\mathit{n}}$

This section presents the characterizations of ideals, minimal ideals, maximal ideals, and principal ideals of $S{K}_n$.

Let $\mathcal{C}$ be a nonempty subset of a power set $P\left(X_n\right)$. The set $\mathcal{C}$ is said to be an upper set of $P\left(X_n\right)$ if $\mathcal{C}$ satisfies the condition that if $A\in \mathcal{C}$ and $A\subseteq B$ for some $B\in P\left(X_n\right)$, then $B\in \mathcal{C}$. Note that if $A\in \mathcal{C}$, then $A\cup B\in \mathcal{C}$ for all $B\in P\left(X_n\right)$.

Now, we present the characterization of ideals of $S{K}_n$ as follows.

Theorem 2.

The ideals of $S{K}_n$ are precisely the sets

$$I_{\mathcal{C}}=\{G\in S{K}_n:V\left(G\right)\in \mathcal{C}\}$$

where $\mathcal{C}$ is an upper set of $P\left(X_n\right)$.

Proof. 

Let $\mathcal{C}$ be an upper set of $P\left(X_n\right)$. We will show that $I_{\mathcal{C}}$ is an ideal of $S{K}_n$. Since $\mathcal{C}\ne \varnothing$, we get $I_{\mathcal{C}}\ne \varnothing$. Let $G\in I_{\mathcal{C}}$ and $H\in S{K}_n$. Then $V\left(G\right)\in \mathcal{C}$ and hence $V\left(GH\right)=V\left(G\right)\cup V\left(H\right)\in \mathcal{C}$ by the previous note which implies that $GH\in I_{\mathcal{C}}$.

Conversely, let I be any ideal of $S{K}_n$ and let $\mathcal{A}=\left\{V\right(G):G\in I\}$. Then $\mathcal{A}$ is a nonempty subset of $P\left(X_n\right)$. We will prove that $\mathcal{A}$ is an upper set of $P\left(X_n\right)$. Let $V\left(G\right)\in \mathcal{A}$ and $A\in P\left(X_n\right)$ in which $V\left(G\right)\subseteq A$. We get that ${\varphi }_{A}G\in I$ since I is an ideal of $S{K}_n$. Thus $A=A\cup V\left(G\right)=V\left({\varphi }_{A}G\right)\in \mathcal{A}$. Hence $\mathcal{A}$ is an upper set of $P\left(X_n\right)$. Therefore, $I_{\mathcal{A}}=\{G\in S{K}_n:V\left(G\right)\in \mathcal{A}\}=\{G\in S{K}_n:G\in I\}=I$. This certainly completes the proof of our assertion. ☐

In what follows, we define a subset of $S{K}_n$,

$$S\left(r\right)=\{G\in S{K}_n:|V\left(G\right)|=r\}\mathrm{where}1\le r\le n,$$

which plays an essential role for characterizing minimal ideals and maximal ideals of $S{K}_n$.

The following lemma shows some facts about ideals of $S{K}_n$ which are useful for proving the next theorem.

Lemma 1.

Let I be an ideal of $S{K}_n$. If $S\left(1\right)\subseteq I$, then $I=S{K}_n$.

Proof. 

We assume that $S\left(1\right)\subseteq I$. Let $T\in S{K}_n$. For each $v\in V\left(T\right)$, we obtain that $T=T{\varphi }_v$. Since ${\varphi }_v\in S\left(1\right)\subseteq I$ and I is an ideal of $S{K}_n$, we have $T\in I$ which certainly implies that $I=S{K}_n$, as required. ☐

An ideal M of a semigroup S is said to be $\mathit{minimal}$ if every ideal I of S contained in M coincides with M. Further, M is said to be $\mathit{maximal}$ if every proper ideal of S containing M coincides with M.

The following results describe the characterizations of minimal ideals and maximal ideals of $S{K}_n$, respectively.

Theorem 3.

$S\left(n\right)$ is the unique minimal ideal of $S{K}_n$.

Proof. 

We first show that $S\left(n\right)$ is an ideal of $S{K}_n$. It is easy to investigate that $\left\{X_n\right\}$ is an upper set. By Theorem 2, we obtain that $I_{\left\{X_n\right\}}$ is an ideal of $S{K}_n$.

$$\begin{array}{cc}\hfill \mathrm{Consider}{I}_{\left\{X_n\right\}}& =\{G\in S{K}_n:V\left(G\right)\in \left\{X_n\right\}\}\hfill \\ & =\{G\in S{K}_n:V\left(G\right)=X_n\}\hfill \\ & =\{G\in S{K}_n:|V\left(G\right)|=n\}\hfill \\ & =S\left(n\right),\hfill \end{array}$$

we can conclude that $S\left(n\right)$ is an ideal of $S{K}_n$. Next, let I be an ideal of $S{K}_n$ such that $I\subseteq S\left(n\right)$. Let $H\in S\left(n\right)$. Thus $V\left(H\right)=V\left(G\right)$ and $H=H{\varphi }_{V\left(G\right)}\in I$ for any $G\in I$ which implies that $S\left(n\right)\subseteq I$. Therefore, $S\left(n\right)=I$, that is, $S\left(n\right)$ is a minimal ideal of $S{K}_n$.

We now let J be a minimal ideal of $S{K}_n$ and $G\in J$. Hence ${\varphi }_{V\left(G\right)}\in J$ and ${\varphi }_{X_n}={\varphi }_{X_n}{\varphi }_{V\left(G\right)}\in J$. Let $K\in S\left(n\right)$. Then $K=K{\varphi }_{X_n}\in J$, we obtain that $S\left(n\right)\subseteq J$. It follows that $S\left(n\right)=J$ by the minimality of J. ☐

Theorem 4.

Maximal ideals of $S{K}_n$ are precisely the sets $S{K}_n\backslash \left\{{\varphi }_v\right\}$ where $v\in X_n$.

Proof. 

We first prove that $S{K}_n\backslash \left\{{\varphi }_v\right\}$ is an ideal of $S{K}_n$. Let T denote the set $S{K}_n\backslash \left\{{\varphi }_v\right\}$ where $v\in X_n$. Let $G\in T$ and $H\in S{K}_n$. Suppose to the contrary that $GH={\varphi }_v$. Then $V\left(G\right)\cup V\left(H\right)=\left\{v\right\}$. Hence $V\left(G\right)=\left\{v\right\}$ which implies that $G={\varphi }_v$, a contradiction. Therefore, $GH\in T$, this means that T is an ideal of $S{K}_n$. It is uncomplicated to investigate that T is maximal.

Next, let I be a maximal ideal of $S{K}_n$. If $S\left(1\right)\subseteq I$, then $I=S{K}_n$ by Lemma 1 which contradicts to the maximality of I. Hence $S\left(1\right)⊈I$, that is, there exists ${\varphi }_v\notin I$ for some $v\in X_n$ which implies that $I\subseteq S{K}_n\backslash \left\{{\varphi }_v\right\}$. Since I is maximal in $S{K}_n$, we can conclude that $I=S{K}_n\backslash \left\{{\varphi }_v\right\}$. ☐

Let S be a semigroup and $a\in S$. The smallest ideal of S containing a is $S^{1}a{S}^1$ where $S^1$ is the monoid obtained from S by adjoining an identity 1 if necessary. We shall call it the principal ideal of S generated by a. The following theorem provides the necessary and sufficient conditions for ideals of $S{K}_n$ to be principal.

Theorem 5.

$I_{\mathcal{C}}$ is a principal ideal of $S{K}_n$ if and only if there exists unique $A\in \mathcal{C}$ such that $\left|A\right|=k$ where $k=min\left\{\right|C|:C\in \mathcal{C}\}$ and $A\subseteq X$ for all $X\in \mathcal{C}$.

Proof. 

Assume that $I_{\mathcal{C}}$ is a principal ideal of $S{K}_n$. Then $I_{\mathcal{C}}=\left(S{K}_n^1\right)G\left(S{K}_n^1\right)$ for some $G\in S{K}_n$. Let $A\in \mathcal{C}$ be such that $\left|A\right|=k$. Suppose that there exists $B\in \mathcal{C}$ such that $\left|B\right|=k$. Hence ${\varphi }_A,{\varphi }_B\in I_{\mathcal{C}}=\left(S{K}_n^1\right)G\left(S{K}_n^1\right)$, that is, ${\varphi }_A=G_{1}G{G}_2$ and ${\varphi }_B=H_{1}G{H}_2$ for some $G_1,G_2,H_1,H_2\in S{K}_n^1.$ Thus $A=V\left(G_1\right)\cup V\left(G\right)\cup V\left(G_2\right)$ and $B=V\left(H_1\right)\cup V\left(G\right)\cup V\left(H_2\right)$ which implies that $V\left(G\right)\subseteq A$ and $V\left(G\right)\subseteq B$. Since $G\in I_{\mathcal{C}}$ and $A,B$ are elements of $\mathcal{C}$ having the minimum cardinality k, we obtain that $A=V\left(G\right)=B$. We next let $X\in \mathcal{C}$. Hence ${\varphi }_X\in I_{\mathcal{C}}$. So there exist $G_3,G_4\in S{K}_n^1$ in which ${\varphi }_X=G_{3}G{G}_4$. Then $X=V\left(G_3\right)\cup V\left(G\right)\cup V\left(G_4\right)$ which implies that $A=V\left(G\right)\subseteq X$, as desired.

Conversely, assume that the conditions hold. Since $A\in \mathcal{C}$, we have ${\varphi }_A\in I_{\mathcal{C}}$ which leads to the fact that $\left(S{K}_n^1\right){\varphi }_A\left(S{K}_n^1\right)\subseteq I_{\mathcal{C}}$. Now, let $G\in I_{\mathcal{C}}$. Then $V\left(G\right)\in \mathcal{C}$ and $A\subseteq V\left(G\right)$ by our assumption. Therefore, $G=G{\varphi }_A{\varphi }_A\in \left(S{K}_n^1\right){\varphi }_A\left(S{K}_n^1\right)$ which follows that $I_{\mathcal{C}}=\left(S{K}_n^1\right){\varphi }_A\left(S{K}_n^1\right)$. Consequently, $I_{\mathcal{C}}$ is a principal ideal of $S{K}_n$ generated by ${\varphi }_A$ which completes the proof of our assertion. ☐

Remark 1.

Let A be a nonempty subset of $X_n$. Define $\mathcal{A}$ to be the family of all supersets of A. By Theorem 5, we can conclude that $I_{\mathcal{A}}$ is a principal ideal of $S{K}_n$. It is not difficult to verify that if $A\ne B$, then $I_{\mathcal{A}}\ne I_{\mathcal{B}}$. Therefore, the number of principal ideals of $S{K}_n$ equals the number of nonempty subsets of $X_n$ which equals $2^n-1$, certainly.

Example 1.

This example illustrates the ideal, minimal ideal, maximal ideal, and principal ideal of $S{K}_3$. All elements of $S{K}_3$ are shown in Figure 1 where each block is an $\mathcal{L}$-class of $S{K}_3$. In addition, we observe that

$$\begin{array}{cc}\hfill S\left(1\right)& =\{G_1,G_2,G_3\},\hfill \\ \hfill S\left(2\right)& =\{G_4,G_5,G_6,G_7,G_8,G_9\}\mathit{and}\hfill \\ \hfill S\left(3\right)& =\{G_{10},G_{11},G_{12},G_{13},G_{14},G_{15},G_{16},G_{17}\}.\hfill \end{array}$$

• $S{K}_3\backslash \{G_2,G_3\}$ is an ideal of $S{K}_3$.
• $S\left(3\right)$ is the unique minimal ideal of $S{K}_3$.
• $S{K}_3\backslash \left\{G_1\right\},S{K}_3\backslash \left\{G_2\right\}$ and $S{K}_3\backslash \left\{G_3\right\}$ are all maximal ideals of $S{K}_3$.
• $\{G_4,G_5,G_{10},G_{11},\dots ,G_{17}\}$ is a principal ideal of $S{K}_3$ generated by $G_4$.

3. Maximal Subsemigroups and a Class of Maximal Congruences of ${\mathit{SK}}_{\mathit{n}}$

This section presents the results of maximal subsemigroups and maximal congruences of $S{K}_n$.

A nonempty proper subset M of a semigroup S is called a maximal subsemigroup if M is a subsemigroup of S and any proper subsemigroup of S containing M must be M.

Theorem 6.

A maximal subsemigroup of $S{K}_n$ is one of the following forms.

(i) 

$S{K}_n\backslash \left\{{\varphi }_v\right\}$ for some $v\in X_n$;

(ii) 

$S{K}_n\backslash \left\{T_{ij}\right\}$ for some $i\ne j$.

Proof. 

We have known that $S{K}_n\backslash \left\{{\varphi }_v\right\}$ is a subsemigroup of $S{K}_n$ for all $v\in X_n$ by Theorem 4. So we need to prove that $S{K}_n\backslash \left\{T_{ij}\right\}$ is a subsemigroup of $S{K}_n$ for any distinct $i,j\in \{1,2,\dots ,n\}$. Let $i\ne j$ and $G,H\in S{K}_n\backslash \left\{T_{ij}\right\}$. Suppose that $GH=T_{ij}$. Thus $V\left(G\right)\cup V\left(H\right)=\{v_i,v_j\}$ and $E\left(GH\right)=\left\{v_i{v}_j\right\}$, that is, $V\left(G\right)$ and $V\left(H\right)$ are subsets of $\{v_i,v_j\}$. If both $E\left(G\right)$ and $E\left(H\right)$ contain $\left\{v_i{v}_j\right\}$, then $E\left(GH\right)\ne \left\{v_i{v}_j\right\}$ which is impossible. Then there exists only one of them containing $\left\{v_i{v}_j\right\}$. Without loss of generality, suppose that $E\left(G\right)$ contains $\left\{v_i{v}_j\right\}$. Since $V\left(G\right)\subseteq \{v_i,v_j\}$, we have $G=T_{ij}$ which is a contradiction. Consequently, $S{K}_n\backslash \left\{T_{ij}\right\}$ is a subsemigroup of $S{K}_n$. It is easy to see that $S{K}_n\backslash \left\{{\varphi }_v\right\}$ and $S{K}_n\backslash \left\{T_{ij}\right\}$ are maximal.

Let S be a maximal subsemigroup of $S{K}_n$. We consider the following two cases.

Case 1:$\{{\varphi }_v:v\in X_n\}\subseteq S$. Then there exists $T_{ij}\in S{K}_n\backslash S$, otherwise $\{T_{ij}:i\ne j\}\subseteq S$ which implies that $S=S{K}_n$ since $\{{\varphi }_v:v\in X_n\}\cup \{T_{ij}:i\ne j\}$ is a generating set of $S{K}_n$, a contradiction. So $S\subseteq S{K}_n\backslash \left\{T_{ij}\right\}$ and by the maximality of S, we get $S=S{K}_n\backslash \left\{T_{ij}\right\}$, that is, S is of the form $\left(\mathrm{ii}\right)$.

Case 2:$\{{\varphi }_v:v\in X_n\}⊈S$. Then ${\varphi }_v\notin S$ for some $v\in X_n$. Thus $S\subseteq S{K}_n\backslash \left\{{\varphi }_v\right\}$ and hence $S=S{K}_n\backslash \left\{{\varphi }_v\right\}$ since S is a maximal subsemigroup of $S{K}_n$. Therefore, S is of the form $\left(\mathrm{i}\right)$. ☐

Let $\rho$ be a congruence on a semigroup S. We call $\rho$ a maximal congruence if $\delta$ is a congruence on S with $\rho ⊊\delta \subseteq S\times S$ implies $\delta =S\times S.$

Theorem 7.

Let $v\in X_n$. Then $\rho =[(S{K}_n\backslash \left\{{\varphi }_v\right\})\times (S{K}_n\backslash \left\{{\varphi }_v\right\})]\cup \left\{({\varphi }_v,{\varphi }_v)\right\}$ is a maximal congruence on $S{K}_n$.

Proof. 

It is clear that ρ is an equivalence relation on $S{K}_n$. Let $G,H,K\in S{K}_n$ be such that $(H,K)\in \rho$. Then $(H,K)\in (S{K}_n\backslash \left\{{\varphi }_v\right\})\times (S{K}_n\backslash \left\{{\varphi }_v\right\})$ or $H={\varphi }_v=K$. If $(H,K)\in (S{K}_n\backslash \left\{{\varphi }_v\right\})\times (S{K}_n\backslash \left\{{\varphi }_v\right\})$, then $GH,GK\in S{K}_n\backslash \left\{{\varphi }_v\right\}$ since $S{K}_n\backslash \left\{{\varphi }_v\right\}$ is an ideal of $S{K}_n$. Thus $(GH,GK)\in$$(S{K}_n$$\backslash \left\{{\varphi }_v\right\})\times (S{K}_n\backslash \left\{{\varphi }_v\right\})$$\subseteq \rho$. If $H={\varphi }_v=K$, then $GH=G{\varphi }_v=GK$. Thus $(GH,GK)\in \rho$ which implies that ρ is a congruence on $S{K}_n$.

Next, we show that ρ is a maximal congruence on $S{K}_n$. Assume that δ is a congruence on $S{K}_n$ such that $\rho ⊊\delta \subseteq S{K}_n\times S{K}_n$. Then there exists $({\varphi }_v,K)\in \delta$ where $K\in S{K}_n\backslash \left\{{\varphi }_v\right\}$. Let $(G,H)\in S{K}_n\times S{K}_n$. If $G,H\in S{K}_n\backslash \left\{{\varphi }_v\right\}$, then $(G,H)\in \rho \subseteq \delta$. If $G={\varphi }_v=H$, then $(G,H)\in \rho \subseteq \delta$. If $G={\varphi }_v$ and $H\in S{K}_n\backslash \left\{{\varphi }_v\right\}$, then $(H,K)\in (S{K}_n\backslash \left\{{\varphi }_v\right\})\times (S{K}_n\backslash \left\{{\varphi }_v\right\})\subseteq \rho \subseteq \delta$. From $({\varphi }_v,K),(K,H)\in \delta$, we obtain by the transitivity of δ that $(G,H)=({\varphi }_v,H)\in \delta$. Thus $\delta =S{K}_n\times S{K}_n$, as required. ☐

4. Natural Order on ${\mathit{SK}}_{\mathit{n}}$

In this section, we prescribe the natural order on $S{K}_n$ and investigate minimal elements and maximal elements of $S{K}_n$ with respect to this order. Furthermore, we consider lower covers and upper covers of elements that are not minimal and maximal, respectively. We also give the necessary and sufficient conditions for the existence of an infimum and a supremum of a nonempty subset of $S{K}_n$.

On an inverse semigroup S, the $\mathit{natural}\mathit{order}$ is defined in a natural way. For given $a,b\in S$, we define $a\le b$ if there exists an idempotent $e\in S$ such that $a=be$. The following theorem characterizes the natural order on $S{K}_n$.

Theorem 8.

Let $G,H\in S{K}_n$. Then $G\le H$ if and only if $V\left(H\right)\subseteq V\left(G\right)$ and $E\left(H\right)=E\left(G\right)$.

Proof. 

Assume that $G\le H$. Then there exists $K\in \mathcal{E}\left(S{K}_n\right)$ such that $G=HK$. Thus $V\left(H\right)\subseteq V\left(H\right)\cup V\left(K\right)=V\left(G\right)$ and

$$\begin{array}{cc}\hfill E\left(G\right)& =\left[E\right(H)\cup E(K\left)\right]\backslash \left[E\right(H)\cap E(K\left)\right]\hfill \\ & =\left[E\right(H)\cup \varnothing ]\backslash \left[E\right(H)\cap \varnothing ]\hfill \\ & =E\left(H\right).\hfill \end{array}$$

Conversely, assume that $V\left(H\right)\subseteq V\left(G\right)$ and $E\left(H\right)=E\left(G\right)$. Therefore, ${\varphi }_{V\left(G\right)}\in \mathcal{E}\left(S{K}_n\right)$. It is obvious that $V\left(G\right)=V\left(H\right)\cup V\left({\varphi }_{V\left(G\right)}\right)=V\left(H{\varphi }_{V\left(G\right)}\right)$ since $V\left(H\right)\subseteq V\left(G\right)$. Since $E\left(G\right)=E\left(H\right)=[E\left(H\right)\cup E\left({\varphi }_{V\left(G\right)}\right)]\backslash [E\left(H\right)\cap E\left({\varphi }_{V\left(G\right)}\right)]=E\left(H{\varphi }_{V\left(G\right)}\right)$, we obtain that $G=H{\varphi }_{V\left(G\right)}$. Consequently, $G\le H$. ☐

In particular, we write $G<H$ for $G\le H$ but $G\ne H$, that is,

$$G<H\mathrm{if}\mathrm{and}\mathrm{only}\mathrm{if}V\left(H\right)⊊V\left(G\right)\mathrm{and}E\left(H\right)=E\left(G\right).$$

Remark 2.

In fact, the order relation ≤ is compatible with the multiplication on a semigroup S which can be seen in [9] $(p.152)$.

Let $(P,\le )$ be a partially ordered set. An element a of P is called $\mathit{minimal}$ if for each $p\in P$, $p\le a$ implies $p=a$. For the definition of a maximal element, we can define in an analogous manner of a minimal element.

We now present the characterizations of minimal elements and maximal elements of $S{K}_n$, respectively.

Theorem 9.

Let $G\in S{K}_n$. Then G is minimal if and only if $V\left(G\right)=X_n$.

Proof. 

Assume that G is minimal. We have known that $V\left(G\right)\subseteq X_n$. Suppose that there exists $v\in X_n\backslash V\left(G\right)$. Let H be a graph such that $V\left(H\right)=V\left(G\right)\cup \left\{v\right\}$ and $E\left(H\right)=E\left(G\right)$. Thus $V\left(G\right)⊊V\left(H\right)$ and then $H<G$ which contradicts to the minimality of G. Hence $V\left(G\right)=X_n$.

Conversely, assume that $V\left(G\right)=X_n$. Let $H\in S{K}_n$ be such that $H\le G$. By Theorem 8, we have $X_n=V\left(G\right)\subseteq V\left(H\right)$ and $E\left(G\right)=E\left(H\right)$. Hence $V\left(H\right)=X_n=V\left(G\right)$ which leads to $H=G$. Therefore, G is minimal. ☐

Theorem 10.

Let $G\in S{K}_n$. Then G is maximal if and only if either $G={\varphi }_v$ for some $v\in X_n$ or G contains no isolated vertices.

Proof. 

Assume that G is maximal. Suppose that $G\ne {\varphi }_v$ for all $v\in X_n$ and G contains an isolated vertex, say v, that is, $\mathrm{deg}\left(v\right)=0$. Let H be a graph such that $V\left(H\right)=V\left(G\right)\backslash \left\{v\right\}$ and $E\left(H\right)=E\left(G\right)$. Then $V\left(H\right)⊊V\left(G\right)$ which implies that $G<H$ by Theorem 8. This contradicts the maximality of G.

Conversely, it is easy to verify that G is maximal when $G={\varphi }_v$ for all $v\in X_n$. Now, we assume that G contains no isolated vertices. Let $H\in S{K}_n$ be such that $G\le H$. Then $V\left(H\right)\subseteq V\left(G\right)$ and $E\left(H\right)=E\left(G\right)$. Let $v\in V\left(G\right)$. Since $\mathrm{deg}\left(v\right)>0$, there exists $u\in V\left(G\right)$ such that $vu\in E\left(G\right)=E\left(H\right)$, and thus $v\in V\left(H\right)$. Hence $V\left(H\right)=V\left(G\right)$ which leads to $H=G$. Therefore, G is maximal in $S{K}_n$. ☐

Let $(P,\le )$ be a partially ordered set. A lower cover of $p\in P$ is an element l of P such that $l<p$ and there is no $l^{\prime }\in P$ in which $l<l^{\prime }<p$. An upper cover of $p\in P$ is an element $u\in P$ such that $p<u$ and there is no $u^{\prime }\in P$ in which $p<u^{\prime }<u$.

The following lemma describes the existence of lower covers and upper covers of elements in $S{K}_n$.

Lemma 2.

Let $G\in S{K}_n$. Then the following statements hold:

(i) 

if G is not minimal, then G has a lower cover;

(ii) 

if G is not maximal, then G has an upper cover.

Proof. 

(i) Let $G\in S{K}_n$ be not minimal. Thus $X_n\backslash V\left(G\right)\ne \varnothing$ by Theorem 9. Let $v\in X_n\backslash V\left(G\right)$. Define H to be a graph with a vertex set $V\left(H\right)=V\left(G\right)\cup \left\{v\right\}$ and an edge set $E\left(H\right)=E\left(G\right)$. Thus $V\left(G\right)⊊V\left(H\right)$ which implies that $H<G$. Suppose that there exists $K\in S{K}_n$ in which $H<K<G$. We obtain that $V\left(G\right)⊊V\left(K\right)⊊V\left(H\right)=V\left(G\right)\cup \left\{v\right\}$, which is impossible. Consequently, H is a lower cover of G.

(ii) Assume that G is not maximal. Then $\left|V\right(G\left)\right|>1$ and G must contain an isolated vertex, say v, by Theorem 10. Define H to be a graph with $V\left(H\right)=V\left(G\right)\backslash \left\{v\right\}$ and $E\left(H\right)=E\left(G\right)$. Then $V\left(H\right)⊊V\left(G\right)$, that is, $G<H$. Suppose that there exists $K\in S{K}_n$ such that $G<K<H$. Hence $V\left(G\right)\backslash \left\{v\right\}=V\left(H\right)⊊V\left(K\right)⊊V\left(G\right)$, which is impossible. Therefore, H is an upper cover of G. ☐

Theorem 11.

Let $G\in S{K}_n$ be such that G is not minimal. Then $H\in S{K}_n$ is a lower cover of G if and only if $V\left(H\right)=V\left(G\right)\cup \left\{v\right\}$ for some $v\in X_n\backslash V\left(G\right)$ and $E\left(H\right)=E\left(G\right)$. Consequently, the number of lower covers of G equals $|X_n\backslash V\left(G\right)|$.

Proof. 

By Lemma 2, G has a lower cover. Assume that H is a lower cover of G. Then $H<G$ which implies that $V\left(G\right)⊊V\left(H\right)$ and $E\left(H\right)=E\left(G\right)$. We will show that $\left|V\right(H)\backslash V(G\left)\right|=1$. Suppose to the contrary that there exist two different vertices $v_1,v_2\in V\left(H\right)\backslash V\left(G\right)$. Define K to be a graph with $V\left(K\right)=V\left(G\right)\cup \left\{v_1\right\}$ and $E\left(K\right)=E\left(G\right)$. Then $V\left(G\right)⊊V\left(K\right)$ which implies that $K<G$. Since $V\left(K\right)=V\left(G\right)\cup \left\{v_1\right\}⊊V\left(G\right)\cup \{v_1,v_2\}\subseteq V\left(H\right)$ and $E\left(K\right)=E\left(H\right)$, we have $H<K$ which is a contradiction. Hence $\left|V\right(H)\backslash V(G\left)\right|=1$. Therefore, $V\left(H\right)=V\left(G\right)\cup \left\{v\right\}$ for some $v\in X_n\backslash V\left(G\right)$.

Conversely, assume that the conditions hold. By the same proof as given in Lemma 2(i), we obtain that H is a lower cover of G. ☐

Now, we define the notation which is useful for proving the following theorem. Let G be a graph and v any vertex of G. Then $G-\left\{v\right\}$ denotes the subgraph of G by deleting the vertex v and all edges of G which are incident with v.

Theorem 12.

Let $G\in S{K}_n$ be such that G is not maximal. Then $H\in S{K}_n$ is an upper cover of G if and only if $H=G-\left\{v\right\}$ where v is an isolated vertex of G. Consequently, the number of upper covers of G equals the number of isolated vertices in G.

Proof. 

By Lemma 2, G has an upper cover. Let $H\in S{K}_n$ be an upper cover of G. Then $G<H$, that is, $V\left(H\right)⊊V\left(G\right)$ and $E\left(H\right)=E\left(G\right)$. It follows that $V\left(G\right)\backslash V\left(H\right)\ne \varnothing$ and every element in $V\left(G\right)\backslash V\left(H\right)$ is an isolated vertex of G. Suppose that $\left|V\right(G)\backslash V(H\left)\right|\ge 2$. Let $v_1,v_2\in V\left(G\right)\backslash V\left(H\right)$ be different. Define K to be the graph such that $V\left(K\right)=V\left(H\right)\cup \left\{v_1\right\}$ and $E\left(K\right)=E\left(G\right)=E\left(H\right)$. Then $V\left(H\right)⊊V\left(K\right)⊊V\left(G\right)$ since $v_2\in V\left(G\right)\backslash V\left(K\right)$. Hence $G<K<H$ which is a contradiction since H is an upper cover of G. Thus $\left|V\right(G)\backslash V(H\left)\right|=1$, that is, $H=G-\left\{v\right\}$ where v is an isolated vertex.

Conversely, let $H=G-\left\{v\right\}$ where v is an isolated vertex. By the same proof as given in Lemma 2(ii), we obtain that H is an upper cover of G. ☐

If X is a nonempty subset of a partially ordered set $(P,\le )$, an element a of P is said to be an infimum of X if a satisfies the following conditions:

(i)

$a\le x$ for every $x\in X$;

(ii)

for each $p\in P$ in which $p\le x$ for all $x\in X$, if $a\le p$, then $a=p$.

Similarly, we leave it to the reader to provide the analogous definition of a supremum of X.

Theorem 13.

Let $\mathcal{A}$ be a nonempty subset of $S{K}_n$. Then $\mathcal{A}$ has an infimum if and only if $E\left(G\right)=E\left(H\right)$ for all $G,H\in \mathcal{A}$.

Proof. 

Assume that $\mathcal{A}$ has an infimum, say N. Hence $N\le G$ for all $G\in \mathcal{A}$ which implies that $E\left(N\right)=E\left(G\right)$ for all $G\in \mathcal{A}$. Thus $E\left(G\right)=E\left(H\right)$ for all $G,H\in \mathcal{A}$.

Conversely, assume that $E\left(G\right)=E\left(H\right)$ for all $G,H\in \mathcal{A}$. Define N to be a graph with a vertex set $V\left(N\right)={\displaystyle \bigcup _{G\in \mathcal{A}}}V\left(G\right)$ and an edge set $E\left(N\right)=E\left(T\right)$ for some $T\in \mathcal{A}$, that is, $E\left(N\right)=E\left(G\right)$ for all $G\in \mathcal{A}$. It is clear that $V\left(G\right)\subseteq V\left(N\right)$ for all $G\in \mathcal{A}$ which implies that $N\le G$ for all $G\in \mathcal{A}$. Let $K\in S{K}_n$ be such that $K\le G$ for all $G\in \mathcal{A}$ and $N\le K$, that is, $V\left(G\right)\subseteq V\left(K\right)\subseteq V\left(N\right)$ and $E\left(N\right)=E\left(G\right)=E\left(K\right)$ for all $G\in \mathcal{A}$. Hence $V\left(N\right)={\displaystyle \bigcup _{G\in \mathcal{A}}}V\left(G\right)\subseteq V\left(K\right)$, it follows that $K=N$. Consequently, N is an infimum of $\mathcal{A}$ which completes the proof of our assertion. ☐

Theorem 14.

Let $\mathcal{A}$ be a nonempty subset of $S{K}_n$. Then $\mathcal{A}$ has a supremum if and only if ${\displaystyle \bigcap _{G\in \mathcal{A}}}V\left(G\right)\ne \varnothing$ and $E\left(G\right)=E\left(H\right)$ for all $G,H\in \mathcal{A}$.

Proof. 

Assume that $\mathcal{A}$ has a supremum, say M. Then $G\le M$ for all $G\in \mathcal{A}$, that is, $V\left(M\right)\subseteq V\left(G\right)$ and $E\left(M\right)=E\left(G\right)$ for all $G\in \mathcal{A}$. Hence $V\left(M\right)\subseteq {\displaystyle \bigcap _{G\in \mathcal{A}}}V\left(G\right)$ which implies that ${\displaystyle \bigcap _{G\in \mathcal{A}}}V\left(G\right)\ne \varnothing$ and $E\left(G\right)=E\left(H\right)$ for all $G,H\in \mathcal{A}$.

Conversely, assume that the statements hold. Let M be a graph such that $V\left(M\right)={\displaystyle \bigcap _{G\in \mathcal{A}}}V\left(G\right)$ and $E\left(M\right)=E\left(H\right)$ for some $H\in \mathcal{A}$. We will show that M is a supremum. It is clear that $V\left(M\right)\subseteq V\left(G\right)$ and $E\left(M\right)=E\left(G\right)$ for all $G\in \mathcal{A}$. Thus $G\le M$ for all $G\in \mathcal{A}$. Next, let $K\in S{K}_n$ be such that $G\le K$ for all $G\in \mathcal{A}$ and $K\le M$. Thus $V\left(M\right)\subseteq V\left(K\right)\subseteq V\left(G\right)$ and $E\left(K\right)=E\left(G\right)=E\left(M\right)$ for all $G\in \mathcal{A}$. It follows that $V\left(K\right)\subseteq {\displaystyle \bigcap _{G\in \mathcal{A}}}V\left(G\right)=V\left(M\right)$ and then $M=K$. This means that M is a supremum of $\mathcal{A}$, as required. ☐

Example 2.

The Figure 2 shows the Hasse diagram of $S{K}_3$ in which elements of $S{K}_3$ are illustrated in Example 1.

5. Conclusions

In summary, we have found that Green’s relations on an inverse semigroup $S{K}_n$ coincide. All ideals, maximal ideals, and principal ideals have been characterized. In particular, the minimal ideal of $S{K}_n$ is unique. Moreover, we have investigated maximal subsemigroups and maximal congruences on $S{K}_n$. Furthermore, the natural order on $S{K}_n$ has been defined for considering the characterizations of minimal and maximal elements in $S{K}_n$. The necessary and sufficient conditions for a nonempty subset of $S{K}_n$ to have an infimum and a supremum have been provided with certainty.