On a Class of Semigroup Graphs

Li Chen¹, Tongsuo Wu²

¹School of Mathematics and Statistics, Yancheng Teachers University, Yancheng, China.
²Department of Mathematics, Shanghai Jiaotong University, Shanghai, China.

DOI: 10.4236/apm.2023.136021                

Abstract

Let G = Γ(S) be a semigroup graph, i.e., a zero-divisor graph of a semigroup S with zero element 0. For any adjacent vertices x, y in G, denote C(x,y) = {z∈V(G) | N (z) = {x,y}}. Assume that in G there exist two adjacent vertices x, y, a vertex s∈C(x,y) and a vertex z such that d (s,z) = 3. This paper studies algebraic properties of S with such graphs G = Γ(S), giving some sub-semigroups and ideals of S. It constructs some classes of such semigroup graphs and classifies all semigroup graphs with the property in two cases.

Keywords

Zero-Divisor Semigroup, Sub-Semigroup, Zero-Divisor Graph

1. Introduction

Throughout, G is a simple and connected graph. For a vertex x of G, the neighborhood of x is denoted as $N\left(x\right)$ , which is the set of all vertices adjacent to x. Denote also $\overline{N\left(x\right)}=N\left(x\right)\cup \left\{x\right\}$ . The cardinality of $N\left(x\right)$ is denoted by deg(x). The vertex x is called an end vertex if $deg\left(x\right)=1$ , and an isolated vertex if $deg\left(x\right)=0$ ( [1] ). Throughout, S is a commutative semigroup with 0. Recall that for a commutative semigroup (or a commutative ring) S with 0, the zero-divisor graph $\Gamma \left(S\right)$ is an undirected graph whose vertices are the zero-divisors of $S\backslash \left\{0\right\}$ , and with two vertices $a\mathrm{,}b$ adjacent in case $ab=0$ ( [2] - [6] ). If $G\cong$ $\Gamma \left(S\right)$ for some semigroup S with zero element 0, then G is called a semigroup graph.

Some fundamental properties and possible algebraic structures of S and graphic structures of $\Gamma \left(S\right)$ were established in [3] [4] [5] among others. For example, it was proved that $\Gamma \left(S\right)$ is always connected, and the diameter of $\Gamma \left(S\right)$ is less than or equal to 3. If $\Gamma \left(S\right)$ contains a cycle, then its core, i.e., the union of the cycles in $\Gamma \left(S\right)$ , is a union of squares and triangles, and any vertex not in the core is an end vertex which is connected to the core by a single edge. In [7] - [11] , the authors continued the study on the sub-semigroup structure and ideal structure of semigroups. Therefore, studying the interplay between the algebraric structures of S and the graph theoretic structures of $G=\Gamma \left(S\right)$ is still a fun problem.

For any adjacent vertices $a\mathrm{,}b$ in $V\left(G\right)$ , denote $C\left(a,b\right)=\left\{x\in V\left(G\right)|N\left(x\right)=\left\{a,b\right\}\right\}$ and let $T_a$ denote the set of all end vertices adjacent to a. In [12] , we discuss the properties of $\Gamma \left(S\right)$ satisfies condition ( $K_p$ ), here we assume $p=3$ and consider the following Δ assumed on $G=\Gamma (\; S\; )$

(Δ) There exist in G two adjacent vertices $a\mathrm{,}b$ , a vertex $s\in C\left(a\mathrm{,}b\right)$ and a vertex z such that $d\left(s\mathrm{,}z\right)=3$ .

In this paper, we study algebraic properties of semigroup S and the graphic structures of $\Gamma \left(S\right)$ such that the condition (Δ) holds for $\Gamma \left(S\right)$ . (We can further assume that triangles and rectangles coexist in the core $K\left[\Gamma \left(S\right)\right]$ .) In particular, it is proved that $S\backslash \left[C\left(a\mathrm{,}b\right)\cup T_a\cup T_b\right]$ is an ideal of S. Under some additional conditions, it is proved that $S\backslash C\left(a\mathrm{,}b\right)$ may be an ideal or a sub-semigroup of S (Theorem 2.4). We also use Theorem 2.4 to construct some classes of semigroup graphs which satisfies the condition (Δ), and give a complete classification of such semigroup graphs in two cases.

We record a known result on finite semigroups to end this part (see e.g., [ [13] , Corollary 5.9 on page 25]). We also include a proof for the completeness.

Lemma 1.1. Any finite nonempty semigroup S contains an idempotent element.

Proof. Take any element x from S and consider the sequence $x\mathrm{,}{x}^2\mathrm{,}{x}^3\mathrm{,}\cdots$ . Since S is a finite set, there exist $m<n$ such that $x^m=x^n$ . Let $r=n-m$ , and take k such that $kr\ge m$ . Then

$x^{kr}=x^m\cdot x^{kr-m}=\left(x^r\cdot x^m\right)x^{kr-m}=x^r\cdot x^{kr}=x^r\left(x^r{x}^{kr}\right)=\cdots ={\left(x^{kr}\right)}^2.$

□

2. Properties of S

Note that, for any $x\in S$ , $Ann\left(x\right)=\left\{y|xy=0,y\in S\right\}$ , thus for any vertex $x\in \Gamma \left(S\right)$ , $N\left(x\right)\subseteq Ann\left(x\right)$ , and $Ann\left(x\right)\subseteq \overline{N\left(x\right)}\cup \left\{0\right\}$ ,we have the following lemma.

Lemma 2.1. Let S be a commutative semigroup with 0, $\Gamma \left(S\right)$ its zero-divisor graph. For any vertex $x\in \Gamma \left(S\right)$ , if there exists a vertex $y\in \Gamma \left(S\right)$ such that $d\left(x\mathrm{,}y\right)=3$ , then $x^2\ne 0$ in S.

Proof. As $d\left(x\mathrm{,}y\right)=3$ , there exist vertices $a\mathrm{,}z\in \Gamma \left(S\right)$ such that $x-a-z-y$ , $xz\ne 0$ and $ay\ne 0$ . If $x^2=0$ , then $x^{2}z=0$ and thus $xz\in Ann\left(x\right)$ . Clearly $xz\in Ann\left(y\right)$ . Then $xz\in Ann\left(x\right)\cap Ann\left(y\right)=\left\{0\right\}$ , a contradiction. □

Part (1) of the following result is contained in [ [7] , Proposition 2.8]. Part (2) is contained in lemma 1.1 from [8] . And we prove it in a different way.

Proposition 2.2. Let $G=\Gamma \left(S\right)$ be a zero-divisor graph of a semigroup S. For a vertex $b\in V\left(G\right)$ , let $T_b=\left\{x\in V\left(G\right)\mathrm{<mo>\; |\; </mo>}xb=\mathrm{0,}x\ne b\mathrm{,}deg\left(x\right)=1\right\}$ .

1) If $b^2\ne 0$ , then $T_b\cup \left\{0\right\}$ is a sub-semigroup of S.

2) If b is not an end vertex and $T_b\ne \varnothing$ , then $\left\{\mathrm{0,}b\right\}$ is an ideal of S.

Proof. (1) We only need consider as $T_b\ne \varnothing$ . If G contains no cycle, then G is either a two-star graph or a star graph by [ [8] , Theorem 1.3]. If G is a star graph, then $T_b=S\backslash \left\{b\mathrm{,0}\right\}$ . For all $x\mathrm{,}y\in T_b$ , we must have $xy\ne b$ , since otherwise $0=xyb=b^2\ne 0$ , a contradiction. This shows that $T_b\cup \left\{0\right\}$ is a sub-semigroup of S when G is a star graph. If G is a two-star graph or a graph with cycles, then $B\ne \varnothing$ where $B=\left\{x\in V\left(G\right)\mathrm{<mo>\; |\; </mo>}deg\left(x\right)\ge \mathrm{2,}xb=0\right\}$ . For all $x\in T_b$ , we have

$x^2\in Ann\left(b\right)=\left\{0\right\}\cup T_b\cup B$

If $x^2\in B$ , denote $x^2=v$ . Then there exists $z\in S\backslash \left\{b\right\}$ such that $zv=0$ . Since $x^{2}z=vz=0$ , we have $xz\in Ann\left(x\right)=\left\{\mathrm{0,}x\mathrm{,}b\right\}$ . Clearly, $xz\ne 0$ . If $xz=x$ , then $v=x^2=x^{2}z=vz=0$ , a contradiction. If $xz=b$ , then $0=xzb=b^2\ne 0$ , another contradiction. So we must have $x^2\in T_b\cup \left\{0\right\}$ . If $\left|T_b\right|\ge 2$ , then exists a vertex $y\in T_b$ such that $x\ne y$ . If $xy\in B$ , denote $xy=v$ . Then there exists $z\in S\backslash \left\{b\right\}$ such that $zv=0$ . As $xyz=0$ , we have $xz\in Ann\left(y\right)=\left\{\mathrm{0,}y\mathrm{,}b\right\}$ and $yz\in Ann\left(x\right)=\left\{0,x,b\right\}$ , and thus $xz=y$ and $yz=x$ . Then $x^2=xyz=vz=0$ . On the other hand, $xy=x^{2}z=0$ , a contradiction. So $xy\in T_b\cup \left\{0\right\}$ , and hence $T_b\cup \left\{0\right\}\le S$ .

(2) Since $T_b\ne \varnothing$ , there exists $x\in T_b$ such that $by\in Ann\left(x\right)=\left\{0,b,x\right\}$ for all $y\in S$ . By assumption, b is not an end vertex and thus there exists $z\in S\backslash \left\{x\right\}$ such that $bz=0$ . Then $by\ne x$ since otherwise, $by=x$ and it implies $0=bzy=zx\ne 0$ , a contradiction. This completes the proof. □

Remark 2.3. In Proposition 2.2(1), the conclusion can not hold if $b^2=0$ .

For a vertex v of a graph G, if v is not an end vertex and there is no end vertex adjacent to v, then v is said to be an internal vertex. We now prove the main result of this section.

Theorem 2.4. Let $G=\Gamma \left(S\right)$ be a semigroup graph satisfying condition (Δ). Then $\left\{\mathrm{0,}a\mathrm{,}b\right\}$ is an ideal of S, and $S\backslash \left[C\left(a\mathrm{,}b\right)\cup T_a\cup T_b\right]$ is an ideal of S. Furthermore,

1) If both a and b are internal vertices, then $S\backslash C\left(a\mathrm{,}b\right)$ is an ideal of S.

2) If a is an internal vertex, while b is not an internal vertex and $b^2\ne 0$ , then $S\backslash C\left(a\mathrm{,}b\right)$ is a sub-semigroup of S.

Proof. Fix some $s\in C\left(a\mathrm{,}b\right)$ and let $B=\left\{x|x\in S,x\notin C\left(a,b\right),d\left(s,x\right)=2\right\}$ , $L=\left\{y|y\in S,d\left(s,y\right)=3\right\}$ . By assumption $L\ne \varnothing$ , $C\left(a\mathrm{,}b\right)\ne \varnothing$ , and $T_a\cup T_b\subset B$ . Notice that there is no end vertex in $B\backslash \left(T_a\cup T_b\right)$ . By [ [3] , Theorem 2.3] or by [ [5] , Theorem 1(2)], $S=\left\{\mathrm{0,}a\mathrm{,}b\right\}\cup C\left(a\mathrm{,}b\right)\cup B\cup L$ and it is a disjoint union of four nonempty subsets. By Lemma 2.1. we have $c^2\ne 0$ , $\forall c\in C\left(a\mathrm{,}b\right)$ , and hence $Ann\left(c\right)=\left\{\mathrm{0,}a\mathrm{,}b\right\}$ . Clearly, $a^2\in Ann\left(c\right)$ , $b^2\in \left\{\mathrm{0,}a\mathrm{,}b\right\}$ and

$\left\{\mathrm{0,}a\mathrm{,}b\right\}\left(B\cup L\right)\subseteq Ann\left(c\right)=\left\{\mathrm{0,}a\mathrm{,}b\right\}\mathrm{.}$

This shows that $\left\{\mathrm{0,}a\mathrm{,}b\right\}$ is an ideal of S.

For any y in L, there exists a vertex $x\in B$ such that $xy=0$ . Then $yS\subseteq Ann\left(x\right)$ while $C\left(a,b\right)\cap Ann\left(x\right)=\varnothing$ . Hence $LS\cap C\left(a\mathrm{,}b\right)=\varnothing$ . Furthermore, for any $s\in S$ , $ys\in \left\{\mathrm{0,}a\mathrm{,}b\right\}\cup L\cup B$ . If $ys\in \left\{\mathrm{0,}a\mathrm{,}b\right\}\cup B$ , then it is clear that $ys\notin T_a\cup T_b$ whether $sy=x$ or not. Thus $LS\cap \left(T_a\cup T_b\right)=\varnothing$ , and hence

$\left(C\left(a,b\right)\cup T_a\cup T_b\right)\cap LS=\varnothing .$

For any vertex $x_1$ in $B\backslash \left(T_a\cup T_b\right)$ , $x_1\notin C\left(a\mathrm{,}b\right)$ and it has degree greater than one. Hence for any $x_1\in B\backslash \left(T_a\cup T_b\right)$ and any $x_2\in S$ , there exists a vertex $u\in B\cup L$ such that $x_{1}u=0$ . Then $x_1{x}_2\in Ann\left(u\right)$ and it implies $x_1{x}_2\notin C\left(a\mathrm{,}b\right)$ . Thus $\left[\left(B\backslash \left(T_a\cup T_b\right)\right)S\right]\cap C\left(a\mathrm{,}b\right)=\varnothing$ . Finally, by [ [5] , Theorem 4], the core of G together with 0 forms an ideal of S. Thus these arguments show that $S\backslash \left[C\left(a\mathrm{,}b\right)\cup T_a\cup T_b\right]$ is an ideal of S.

1) If both a and b are internal vertices, then $S\backslash C\left(a\mathrm{,}b\right)=S\backslash \left[C\left(a\mathrm{,}b\right)\cup T_a\cup T_b\right]$ . In this case, $S\backslash C\left(a\mathrm{,}b\right)$ is clearly an ideal of S.

2) Now assume that b is not an internal vertex, and $b^2\ne 0$ . Again let $T_b$ be the set of end vertices adjacent to b. By the above discussion, we already have $\left(\left[\left\{\mathrm{0,}a\mathrm{,}b\right\}\cup L\cup \left(B\backslash T_b\right)\right]S\right)\cap C\left(a\mathrm{,}b\right)=\varnothing$ . Since $b^2\ne 0$ , we have $T_b^2\le T_b\cup \left\{0\right\}$ by Theorem 2.2(1). These facts show that $S\backslash C\left(a\mathrm{,}b\right)$ is a sub-semigroup of S, and it completes the proof. □

Remarks 2.5. In Theorem 2.4, if there is no $z\in V\left(G\right)$ such that $d\left(s\mathrm{,}z\right)=$ $3$, then the theorem may not hold. An example is contained in Example 3.1.

3. Some Examples and Complete Classifications of the Graphs in Two Cases

In this section, we use Theorem 2.4 to study the correspondence of zero-divisor semigroups and several classes of graphs satisfying the four necessary conditions of [ [5] , Theorem 1] as well as the general assumption of Theorem 2.4.

Example 3.1. Consider the graph G in Figure 1, where both U and V consist of end vertices. We claim that each graph in Figure 1 is a semigroup graph.

In fact, first notice that $d\left(y_i,V\right)=3$ , $C\left(a,b\right)=\left\{y_1,\cdots ,y_m\right\}$ , and $C\left(a\mathrm{,}d\right)=\left\{x_1\mathrm{,}\cdots \mathrm{,}{x}_n\right\}$ . By Theorem 2.4, if G has a corresponding semigroup $S=V\left(G\right)\cup \left\{0\right\}$ , then the subset $S\backslash \left(\left\{y_1\mathrm{,}\cdots \mathrm{,}{y}_m\right\}\cup U\right)$ must be an ideal of S. If further $a^2\ne 0$ , then $S\backslash \left\{y_1\mathrm{,}\cdots \mathrm{,}{y}_m\right\}$ is a sub-semigroup of S. Also by [ [7] , Theorem 2.1], $S\backslash \left(\left\{y_1\mathrm{,}\cdots \mathrm{,}{y}_m\right\}\cup U\cup V\right)$ is a sub-semigroup of $S\backslash \left(\left\{y_1\mathrm{,}\cdots \mathrm{,}{y}_m\right\}\cup U\right)$ , and thus a sub-semigroup of S.

For $m=2,n=2$ , $U=\left\{u\right\}$ and $V=\left\{v\mathrm{,}\bar{v}\right\}$ , it is not very hard to construct a semigroup T such that $\Gamma \left(T\right)=G-\left\{y_1\mathrm{,}{y}_2\right\}$ following the way mentioned above.

Figure 1. A class of semigroup graph with both U and V consist of end vertices.

Then after a rather complicated calculation, we succeed in adding two vertices $y_1\mathrm{,}{y}_2$ to this table such that $\Gamma \left(S\right)=G$ . The multiplication on S is listed in Table 1 and the detailed verification for the associativity is omitted here:

Notice that $S\backslash \left\{x_1\mathrm{,}{x}_2\right\}$ is not a sub-semigroup of S since $uv=x_1$ . Notice also that $S\backslash \left(U\cup \left\{x_1\mathrm{,}{x}_2\mathrm{,}\cdots \mathrm{,}{x}_n\right\}\right)$ is a sub-semigroup of S.

We remark that the construction in Table 1 can be routinely extended for all $n\ge 1$ , $m\ge 1$ , $\left|U\right|\ge 0$ and $\left|V\right|\ge 0$ , where each of $m\mathrm{,}n\mathrm{,}\left|U\right|\mathrm{,}\left|V\right|$ could be a finite or an infinite cardinal number. In other words, each graph in Figure 1 has a corresponding semigroup for any finite or infinite $n\ge 1$ , $m\ge 1$ , $\left|U\right|\ge 0$ and $\left|V\right|\ge 0$ .

Remark 3.2. Consider the graph G in Figure 1 and assume that $n\ge 1$ , $m\ge 1$ , $\left|U\right|\ge 0$ , $\left|V\right|\ge 1$ .

1) If we add an end vertex w which is adjacent to b, then the resulting graph $\bar{G}$ has no corresponding zero-divisor semigroup, even if $U=\varnothing$ .

2) If we add a vertex w such that $N\left(w\right)=\left\{b\mathrm{,}d\right\}$ , then the resulting graph H has no corresponding zero-divisor semigroup, even if $U=\varnothing$ .

Proof. (1) Assume $v\in V$ . We only need consider the case when $U=\varnothing$ . Suppose that $\bar{G}$ is the zero-divisor graph of a semigroup S with $V\left[\Gamma \left(S\right)\right]=$ $V\left(\bar{G}\right)$. By Proposition 2.2(2), we have $b{x}_1=bv=b$ and $d{y}_1=dw=d$ . Clearly, $aw\mathrm{,}av\in Ann\left(x_1\right)\cap Ann\left(y_1\right)=\left\{a\mathrm{,0}\right\}$ , and thus $aw=a$ and $av=a$ . As $awv=$ $av=a$, we have $wv\in \left[Ann\left(b\right)\cap Ann\left(d\right)\right]\backslash Ann\left(a\right)$ . That means $wv=a$ and $a^2\ne 0$ . We have $y_{1}wv=y_{1}a=0$ and $x_{1}wv=x_{1}a=0$ . Thus $y_{1}w=x_{1}w=d$ and $y_{1}v=x_{1}v=b$ by Lemma 2.1. Consider $x_1{y}_{1}v$ . We have $b=x_{1}b=x_1\left(y_{1}v\right)=$ $y_1\left(x_{1}v\right)=y_{1}b=0$, a contradiction. The contradiction shows that $\bar{G}$ has no corresponding semigroup.

(2) Assume $v\in V$ . We only need consider the case $U=\varnothing$ . Suppose that H is the zero-divisor graph of a semigroup S. We have $bS\subseteq Ann\left(y\right)\cap Ann\left(w\right)\subseteq \left\{\mathrm{0,}b\right\}$ . Clearly,

Table 1. The associative multiplication table of S in Example 3.1.

$wv\in \left[Ann\left(d\right)\cap Ann\left(b\right)\right]\backslash Ann\left(a\right)\subseteq \left\{a\mathrm{,}w\right\}$ since $wva=wa=a$ . If $wv=a$ , then we have $wv{x}_1=a{x}_1=0$ and $wv{y}_1=a{y}_1=0$ , which means $w{x}_1\mathrm{,}w{y}_1\in Ann\left(v\right)\subseteq \left\{\mathrm{0,}v\mathrm{,}d\right\}$ . As $w{x}_1\mathrm{,}w{y}_1\in Ann\left(a\right)\backslash \left\{0\right\}$ , we have $w{x}_1=w{y}_1=d$ . Then $0=d{x}_1=w{y}_1{x}_1=y_{1}d=d$ , a contradiction. Now assume $wv=w$ and consider $w{x}_1$ . $w{x}_1\in Ann\left(a\right)\cap Ann\left(d\right)\cap Ann\left(b\right)\subseteq \left\{\mathrm{0,}a\mathrm{,}b\mathrm{,}d\right\}$ . We claim $w{x}_1\ne d$ since otherwise, $d=w{x}_1=wv\cdot x_1=w{x}_1\cdot v=dv=0$ , a contradiction. In a similar way we prove $w{y}_1\in \left\{a\mathrm{,}b\right\}$ . Moreover, $w{y}_1\cdot x_1=y_1\cdot w{x}_1=0$ whether $w{x}_1=a$ or $w{x}_1=b$ . Thus $w{y}_1=a$ . As $x_1^{2}w=y_1^{2}w=x_1{y}_{1}w=0$ , we have $x_1{y}_1\mathrm{,}{x}_1^2\mathrm{,}{y}_1^2\in Ann\left(a\right)\cap Ann\left(w\right)\subseteq \left\{b\mathrm{,}d\mathrm{,0}\right\}$ , but $x_1{y}_1\ne 0$ . Now consider $x_1{y}_1$ . We conclude $x_1{y}_1=d$ since otherwise, $x_1{y}_1=b$ and it implies $b=b{x}_1=x_1{y}_1{x}_1=x_1^2{y}_1\ne b$ , a contradiction. Finally, $x_1{y}_1=d$ implies $d=d{y}_1=y_1{x}_1{y}_1=x_1{y}_1^2\in \left\{0,b\right\}$ , a contradiction. This completes the proof.

□

Now come back to the structure of semigroup graphs G satisfying the main assumption in Theorem 2.4. We use notations used in its proof. The vertex set of the graph was decomposed into four mutually disjoint nonempty parts, i.e., $V\left(G\right)=\left\{a,b\right\}\cup C\left(a,b\right)\cup B\cup L$ , where after taking a c in $C\left(a,b\right)$

$B=\left\{v\in V\left(G\right)|v\notin C\left(a,b\right),d\left(c,v\right)=2\right\},L=\left\{v\in V\left(G\right)|d\left(c,v\right)=3\right\}.$

(For example, for the graph G in Figure 1, $C\left(a\mathrm{,}b\right)=\left\{y_j\right\}$ , $B=$ $U\cup \left\{d\right\}\cup \left\{x_i\right\}$, $L=V$ . In particular, L consists of end vertices.) By [ [5] , Theorem 1(4)], for each pair $x\mathrm{,}y$ of nonadjacent vertices of G, there is a vertex z with $N\left(x\right)\cup N\left(y\right)\subseteq \overline{N\left(z\right)}$ . Then we have the following observations:

(1) No two vertices in L are adjacent in G. Thus a vertex of L is either an end vertex or is adjacent to at least two vertices in B. In particular, the subgraph induced on L is a completely discrete graph.

(2) A vertex in B is adjacent to either a or b. If a vertex k in B is adjacent to a vertex l in L, then k is adjacent to both a and b. Thus B consists of four parts: end vertices in T_a that are adjacent to a, end vertices in T_b that are adjacent to b, vertices in B₂ that are adjacent to both a and b, and vertices in B₁ that are adjacent to one of $a\mathrm{,}b$ and at the same time adjacent to another vertex in B. By Example 3.1, the structure of the induced subgraph on $B_1\cup B_2$ seems to be complicated. In the following, we will give a complete classification of the semigroup graphs G with $\left|B_1\cup B_2\right|\le 2$ .

First, consider the case $\left|B_1\cup B_2\right|=1$ .

Theorem 3.3. Let G be a graph satisfying condition (Δ). Assume further that $\left|B\backslash \left(T_a\cup T_b\right)\right|=1$ . Then G is a semigroup graph if and only if the following conditions hold:

1) $1\le \left|C\left(a\mathrm{,}b\right)\right|\le \infty$ , $1\le \left|W\right|\le \infty$ and W consists of end vertices, where $W=\left\{s\in V\left(G\right)|d\left(c_1,s\right)=3\right\}$ .

2) either $T_a=\varnothing$ or $T_b=\varnothing$ . (see Figure 2 with $V=\varnothing$ .)

Proof. As $\left|B\backslash \left(T_a\cup T_b\right)\right|=1$ , $B\backslash \left(T_a\cup T_b\right)=B_2$ . By the previous observations, we need only prove the following two facts.

1) If $\left|T_a\right|\ge 0$ and $T_b=\varnothing$ , then G is a subgraph of Figure 1 with $C\left(a\mathrm{,}d\right)=\varnothing$ . (see also Figure 2 with $V=\varnothing$ .) We claim that G is a semigroup graph. In fact, if $U=\varnothing$ , delete the three rows and the three columns involving $x_1\mathrm{,}{x}_2$ and u in Table 1 to obtain an associative multiplication on $S_1=S\backslash \left(U\cup \left\{x_1\mathrm{,}{x}_2\mathrm{,}\cdots \mathrm{,}{x}_n\right\}\right)$ . Clearly, $\Gamma \left(S_1\right)=G$ for $\left|C\left(a,b\right)\right|=2=\left|V\right|$ , $\left|C\left(a,d\right)\right|=0=\left|U\right|$ in Figure 1. Also, the table can be extended for any finite or infinite $\left|C\left(a,b\right)\right|\ge 1$ and $\left|V\right|\ge 0$ while $\left|U\right|=0$ . If $\left|U\right|>0$ , then we work out a corresponding associative multiplication table listed in Table 2, for $C\left(a\mathrm{,}b\right)=\left\{y_1\mathrm{,}{y}_2\right\}$ , $U=\left\{u_1\mathrm{,}{u}_2\right\}$ , $W=\left\{v_1\mathrm{,}{v}_2\right\}$ in Figure 2.

Clearly, the table can be extended for all finite or infinite $\left|C\left(a,b\right)\right|\ge 1$ , $\left|U\right|\ge 1$ and $\left|V\right|\ge 1$ . This completes the proof. □

(2) If both $\left|T_a\right|>0$ and $\left|T_b\right|>0$ , then we conclude that G is not a semigroup graph.

In fact, in this case, G is a graph in Figure 2, where $\left|W\right|\ge 1$ , $\left|U\right|\ge 1$ , $\left|V\right|\ge 1$ . Assume $u\in U$ , $v\in V$ , $w\in W$ and $c\in C\left(a,b\right)$ . We now proceed to prove that such a graph does not have a corresponding semigroup.

Suppose that G is the zero-divisor graph of a semigroup S with $V\left[\Gamma \left(S\right)\right]=V\left(G\right)$ . By Proposition 2.2(2), we have $du=dv=d{c}_1=d$ . Then $u{c}_{1}d=ud=d$ , which implies $u{c}_1\in \left[Ann\left(a\right)\cap Ann\left(b\right)\right]\backslash Ann\left(d\right)\subseteq \left\{c_i\mathrm{,}d\right\}$ .

Figure 2. A class of graph satisfying condition ( $\Delta$ ) and $\left|B/\left(Ta\cup Tb\right)\right|=1$ .

Table 2. The associative multiplication table of S for |U| > 0.

Assume $u{c}_1=d$ . Then $u{c}_{1}w=dw=0$ , and thus $c_{1}w=a$ by Lemma 2.1. As $c_{1}wv=av=a$ , we have $wv\in \left[Ann\left(d\right)\cap Ann\left(b\right)\right]\backslash Ann\left(c_1\right)\subseteq \left\{d\right\}$ , thus $wv=d$ . Then $a=wv{c}_1=d{c}_1=d$ , a contradiction.

So $u{c}_1=c_i$ , and therefore $wu{c}_1=w{c}_i\ne 0$ . We have

$wu\in \left[Ann\left(a\right)\cap Ann\left(d\right)\right]\backslash Ann\left(c_1\right)\subseteq \left\{d\right\}\mathrm{,}$

and thus $wu=d$ . Then $b=bw=buw=bd=0$ , a contradiction. This completes the proof. □

A natural question arising from Example 3.1 is if L only consists of end vertices. The following example shows this is not the case.

Example 3.4. Consider the graph G in Figure 3, where $C\left(a\mathrm{,}b\right)=\left\{c_1\mathrm{,}{c}_2\mathrm{,}\cdots \mathrm{,}{c}_m\right\}$ , $L=\left\{y_1\mathrm{,}{y}_2\mathrm{,}\cdots \mathrm{,}{y}_n\right\}$ , $B=\left\{x_1\mathrm{,}{x}_2\right\}\cup V$ ( $m\ge 1$ , $n\ge 1$ , $\left|V\right|\ge 0$ ) and V consists of end vertices adjacent to b. Notice that each of $m\mathrm{,}n$ and $\left|V\right|$ could be finite or infinite. We conclude that each graph in Figure 3 has a corresponding zero-divisor semigroup.

Proof. We need only work out a corresponding associative multiplication table for $\left|V\right|=m=n=2$ . We use Theorem 2.4 and list the associative multiplication in Table 3. Clearly, the table can be extended for all finite or infinite $m\mathrm{,}n\ge 1$ , and $\left|V\right|\ge 0$ .

This completes the proof.

□

We have three remarks to Example 3.4.

(1) Let $n\ge \mathrm{1,}m\ge 1$ . If we add to G in Figure 3 an end vertex u such that $au=0$ , then the resulting graph $\bar{G}$ has no corresponding zero-divisor semigroup.

Proof. (1) Suppose to the contrary that $\bar{G}$ is the zero-divisor graph of a semigroup P with $V\left[\Gamma \left(P\right)\right]=V\left(\bar{G}\right)$ . By Proposition 2.2(2), we have $a^2\in \left\{\mathrm{0,}a\right\}$ and $b^2\in \left\{\mathrm{0,}b\right\}$ . First, we have $v_1{y}_1\in Ann\left(b\right)\cap Ann\left(x_1\right)\cap Ann\left(x_2\right)=\left\{a\mathrm{,}b\mathrm{,0}\right\}$ and similarly, $u{y}_1\mathrm{,}{c}_1{y}_1\in \left\{a\mathrm{,}b\right\}$ . Then $v_1{y}_1=a$ and $a^2=a$ since

$a{v}_1{y}_1=a{y}_1=a$ . On the other hand, $au{y}_1=0$ and it implies $u{y}_1=b$ . Similarly,

Figure 3. A class of semigroup graph with B₂ = {x₁, x₂}.

Table 3. The associative multiplication table of S in Example 3.4.

we have $c_1{y}_1=b$ . Consider $c_{1}u{y}_1$ . We have $b=ub=u\left(c_1{y}_1\right)=c_1\left(u{y}_1\right)=c_{1}b=0$ , a contradiction. This completes the proof. □

(2) Let $n\ge \mathrm{1,}m\ge 1$ . If we add to G in Figure 3 an end vertex y such that $y{x}_1=0$ , then the resulting graph $\bar{G}$ has no corresponding zero-divisor semigroup, whether or not $T_b=\varnothing$ .

Proof. (2) Assume $\left\{y_1\mathrm{,}y\right\}\subseteq L$ , where y is an end vertex adjacent to $x_1$ . Suppose to the contrary that $\bar{G}$ is the zero-divisor graph of a semigroup P with $V\left[\Gamma \left(P\right)\right]=V\left(\bar{G}\right)$ . First, $x_{2}y\in Ann\left(a\right)\cap Ann\left(x_1\right)\cap Ann\left(y_1\right)=\left\{x_1,0\right\}$ . Thus $x_{2}y=x_1$ , and hence $x_1^2=0$ . By Proposition 2.2(2), we have $c_1{x}_1=x_1$ and therefore, $c_1^2{x}_1=x_1$ . Thus $c_1^2\in \left\{c_i\mathrm{,}{x}_2\mathrm{<mo>\; |\; </mo>}i\right\}$ . We have $c_1^2{y}_1=0$ since $c_1{y}_1\in Ann\left(a\right)\cap Ann\left(x_1\right)\cap Ann\left(x_2\right)=\left\{a,b,0\right\}$ . Since $c_1^2=x_2$ , $c_{1}y\in \left\{a\mathrm{,}b\mathrm{,}{x}_1\right\}$ and $c_1^{2}y=x_{2}y=x_1$ , it follows that $c_{1}y=x_1$ . Finally, $c_{1}y{y}_1=x_1{y}_1=0$ and by Lemma 2.1, we have $c_1{y}_1=x_1$ , contradicting $c_1{y}_1\in \left\{a\mathrm{,}b\right\}$ . This completes the proof.

□

(3) Let $n\ge \mathrm{1,}m\ge 1$ and assume $V=\varnothing$ in Figure 3. If further we add to G an edge connecting $x_1$ and $x_2$ , then the resulting graph $\bar{G}$ has no corresponding zero-divisor semigroup.

Proof. Suppose to the contrary that $\bar{G}$ is the zero-divisor graph of a semigroup P with $V\left[\Gamma \left(P\right)\right]=V\left(\bar{G}\right)$ . By Lemma 2.1, we have $c_1{x}_1\in Ann\left(y_1\right)=\left\{x_1\mathrm{,}{x}_2\mathrm{,0}\right\}$ and similarly, $c_1{x}_2\in \left\{x_1\mathrm{,}{x}_2\right\}$ . Then we have $c_1^2{x}_1\ne 0$ and $c_1^2{x}_2\ne 0$ , which means $c_1^2\in \left[Ann\left(a\right)\cap Ann\left(b\right)\right]\backslash \left[Ann\left(x_1\right)\cup Ann\left(x_2\right)\right]=\left\{c_i|i=1,2,\cdots ,m\right\}$ since $c_1^2\ne 0$ by Lemma 2.1. Similarly, we have $y_1^2\in \left\{y_i|i=1,2,\cdots ,n\right\}$ . Clearly, we have $c_1{y}_1\in Ann\left(a\right)\cap Ann\left(x_1\right)\subseteq \left\{a\mathrm{,}b\mathrm{,}{x}_1\mathrm{,}{x}_2\mathrm{,0}\right\}$ . Then as $c_1^2{y}_1=c_i{y}_1\ne 0$ for some $i\in \left\{\mathrm{1,2,}\cdots \mathrm{,}m\right\}$ , we have $c_1{y}_1\in \left\{x_1\mathrm{,}{x}_2\right\}$ . Finally, $0=\left(c_1{y}_1\right)y_1=c_1{y}_1^2=c_1{y}_i\ne 0$ (for some $i\in \left\{\mathrm{1,2,}\cdots \mathrm{,}n\right\}$ ), a contradiction. This completes the proof. □

Combining the above results, we now classify all semigroup graphs satisfying the main assumption of Theorem 2.4 with $\left|B_1\cup B_2\right|=2$ :

Theorem 3.5. Let G be a graph satisfying condition (Δ). Assume further $\left|B\backslash \left(T_a\cup T_b\right)\right|=2$ .

(1) If $B_2=B\backslash \left(T_a\cup T_b\right)$ , then G is a semigroup graph if and only if G is a graph in Figure 3, where $1\le m\le \infty$ , $1\le n\le \infty$ and $0\le \left|V\right|\le \infty$ .

(2) If $\left|B_2\right|=1$ , then G is a semigroup graph if and only G is a graph in Figure 1, where $n=1$ , $1\le m\le \infty$ $0\le \left|V\right|\le \infty$ , $0\le \left|U\right|\le \infty$ .

Proof. (1) By Example 3.4, each graph in Figure 3 is a semigroup graph. Clearly, $B_2=B\backslash \left(T_a\cup T_b\right)$ and it consists of two vertices. Conversely, the result follows from [ [7] , Theorem 2.1] and the three remarks after Example 3.4.

(2) If $\left|B_2\right|=1$ , then assume $B\backslash \left(T_a\cup T_b\right)=\left\{x_1\mathrm{,}{x}_2\right\}$ , where $a-x_2-b$ . In this case, $x_1-x_2$ in G. If $x_1-a$ in G, then there is no end vertex adjacent to $x_1$ . In this subcase, G is a semigroup graph if and only if $T_b=\varnothing$ by Example 3.1 and Remark 3.2(1), the case of $\left|C\left(a,d\right)\right|=1$ . The other subcase is $x_1-b$ in G, and it is the same with the above subcase. This completes the proof.

□

It is natural to ask the following question: Can one give a complete classification of semigroup graphs $G=\Gamma \left(S\right)$ with $\left|B_1\cup B_2\right|=n$ for any $n\ge 3$ ? At present, it seems to be a rather difficult question.

Add two end vertices to two vertices of the complete graph K_n to obtain a new graph, and denote the new graph as $K_n+2$ . By [ [14] , Theorem 2.1], $K_n+2$ has a unique zero-divisor semigroup S such that $\Gamma \left(S\right)\cong K_n+2$ for each $n\ge 4$ . Having Theorem 2.4 in mind, it is natural to consider graphs obtained by adding some caps to $K_n+2$ .

Example 3.6. Consider the graph G in Figure 4. The subgraph G₁ induced on the vertex subset $S^{\mathrm{<mo>\; *\; </mo>}}=\left\{a\mathrm{,}b\mathrm{,}{x}_1\mathrm{,}{x}_2\mathrm{,}{y}_1\mathrm{,}{y}_2\right\}$ is the graph $K_4+2$ , i.e., K₄ together with two end vertices $y_1\mathrm{,}{y}_2$ . Then G₁ has a unique corresponding zero-divisor semigroup $S=S^{*}\cup \left\{0\right\}$ by [ [15] , Theorem 2.1]. We can work out the corresponding associative multiplication table, and list it in Table 4.

(1) If we add to G₁ a vertex c such that $N\left(c\right)=\left\{a,b\right\}$ , then the resulting graph H₁ has no corresponding zero-divisor semigroup.

(2) If we add to G₁ a vertex d such that $N\left(d\right)=\left\{a,x_1\right\}$ , then the resulting

Figure 4. “caps” added to K₄ + 2.

Table 4. The associative multiplication table of K₄ + 2.

graph H₂ has no corresponding zero-divisor semigroup.

(3) If we add to G₁ vertices $c_i$ ( $i\in I$ ) such that $N\left(c_i\right)=\left\{x_1\mathrm{,}{x}_2\right\}$ , then the resulting graph H has corresponding zero-divisor semigroups, where I could be any finite or infinite index set.

In each of the above three cases, we say that a cap is added to the subgraph $K_4+2$ .

Proof. (1) Suppose that H₁ is the zero-divisor graph of a semigroup S₁ with $V\left[\Gamma \left(S_1\right)\right]=V\left(H_1\right)$ . Then by Theorem 2.4, S is an ideal of $S_1=S\cup \left\{c\right\}$ . Thus we only need check the associative multiplication of S₁ based on the table of S already given in Table 4. First, we have $c{x}_2=x_2$ by Proposition 2.2(2). Consider $y_{1}bc$ . Clearly, $0=0y_1=\left(cb\right)y_1=c\left(b{y}_1\right)=c{x}_2=x_2$ , a contradiction. This completes the proof.

(2) Suppose that H₂ is the zero-divisor graph of a semigroup $S_2=S\cup \left\{d\right\}$ with $V\left[\Gamma \left(S_2\right)\right]=V\left(H_2\right)$ . If $x_1^2\ne 0$ , then by Theorem 2.4(2), S is a sub-semigroup of S₂. Then $\Gamma \left(S\right)=K_4+2$ , and it implies $x_1^2=0$ by Table 4, a contradiction.

Table 5. The associative multiplication table of K₄ + 2 with some caps on x₁, x₂.

In the following we assume $x_1^2=0$ .

By Lemma 2.1, we have $d^2\ne 0$ , and thus $a{y}_1\mathrm{,}a{y}_2\in Ann\left(d\right)=\left\{a\mathrm{,}{x}_1\mathrm{,0}\right\}$ . Clearly $a{y}_1\ne 0$ and we can have $a{y}_2=a$ . (Otherwise, $a{y}_2=x_1$ and we have $0=x_1{y}_1=a{y}_2{y}_1=\left(a{y}_1\right)y_2\ne 0$ , a contradiction.) Then $a{y}_1{y}_2\ne 0$ , and thus $y_1{y}_2\in \left[Ann\left(x_1\right)\cap Ann\left(x_2\right)\right]\backslash Ann\left(a\right)$ . It means $y_1{y}_2=a$ and $a^2\ne 0$ . Clearly $b{y}_1{y}_2=0$ , and thus $b{y}_1=x_2$ , $b{y}_2=x_1$ by Lemma 2.1. Similarly, $c{y}_1{y}_2=ca=0$ and thus $c{y}_1=x_2$ , $c{y}_2=x_1$ . Finally, consider $bc{y}_1$ . We have $0=b{x}_2=b\left(c{y}_1\right)=c\left(b{y}_1\right)=c{x}_2=x_2$ , a contradiction. This completes the proof.

(3) Suppose that H is the subgraph of G in Figure 4 induced on the vertex set $S^{\mathrm{<mo>\; *\; </mo>}}\cup \left\{c_i\mathrm{<mo>\; |\; </mo>}i\in I\right\}$ . Assume that H is the zero-divisor graph of a semigroup P with $V\left[\Gamma \left(P\right)\right]=V\left(H\right)$ . Clearly, it dose not satisfy the condition of Theorem 2.4. For $\left|I\right|=2$ , we work out an associative multiplication table and list it in Table 5:

The table can be easily extended for any finite or infinite index set I. □

We remark that in Example 3.6, replace K₄ by K_n for any $n\ge 5$ , the results still hold. There exists no difficulty to generalize the proofs to the general cases. Thus we have proved the following general result.

Theorem 3.7. Assume $n\ge 4$ and let $G=K_n+2$ be the complete graph K_n together with two end vertices. Add some (finite or infinite) caps to the subgraph K_n to obtain a new graph H such that G is a subgraph of H. Then H is a semigroup graph if and only if each of the gluing vertices is adjacent to an end vertex in G.

Fund

This research is supported by the National Natural Science Foundation of China (Grant No.11201407, No.11271250.), Natural Science Foundation of Jiangsu Province (Grant No. BK2012245).

Conflicts of Interest

The authors declare no conflicts of interest regarding the publication of this paper.

References

[1]	Buckley, F. and Lewinter, M. (2003) A Friendly Introduction to Graph Theory. Prentice-Hall, New York.
[2]	Beck, I. (1988) Coloring of Commutative Rings. Journal of Algebra, 116, 208-226. https://doi.org/10.1016/0021-8693(88)90202-5
[3]	Anderson, D.F. and Livingston, P.S. (1999) The Zero-Divisor Graph of a Commutative ring. Journal of Algebra, 217, 434-447. https://doi.org/10.1006/jabr.1998.7840
[4]	Anderson, D.F., Levy, R. and Shapiro, J. (2003) Zero-Divisor Graphs, von Neumann Regular Rings, and Boolean Algebras. Journal of Pure and Applied Algebra, 180, 221-241. https://doi.org/10.1016/S0022-4049(02)00250-5
[5]	DeMeyer, F.R. and DeMeyer, L. (2005) Zero-Divisor Graphs of Semigroups. Journal of Algebra, 283, 190-198. https://doi.org/10.1016/j.jalgebra.2004.08.028
[6]	Chen, L. and Wu, T.S. (2010) Some Refinements of Star Graphs Whose Semigroup S Satisfies S3 = 0. Communications in Algebra, 38, 2499-2512. https://doi.org/10.1080/00927870903399885
[7]	Wu, T.S. and Lu, D.C. (2008) Sub-Semigroups Determined by the Zero-Divisor Graph. Discrete Mathematics, 308, 5122-5135. https://doi.org/10.1016/j.disc.2007.09.032
[8]	DeMeyer, F.R., McKenzie, T. and Schneider, K. (2002) The Zero-Divisor Graph of a Commutative Semigroup. Semigroup Forum, 65, 206-214. https://doi.org/10.1007/s002330010128
[9]	Baziar, M., Momtahan, E. and Safaeeyan, S. (2014) Zero-Divisor Graph of Abelian Groups. Journal of Algebra and Its Applications, 13, Article ID: 1450007. https://doi.org/10.1142/S0219498814500078
[10]	Lu, D.C. and Wu, T.S. (2009) On Bipartite Zero-Divisor Graphs. Discrete Mathematics, 309, 755-762. https://doi.org/10.1016/j.disc.2008.01.044
[11]	Liu, Q. and Wu, T.S. (2011) Zero-Divisor Graphs Whose Cores Contain No Rectangles. Algebra Colloquium, 18, 675-684. https://doi.org/10.1142/S1005386711000526
[12]	Chen, L. and Wu, T.S. (2011) On Rings R Whose Graphs Γ(R) Satisfy Condition (Kp). Journal of Algebra and Its Applications, 10, 665-674. https://doi.org/10.1142/S0219498811004835
[13]	Grillet, P.A. (2001) Commutative Semigroups. Kluwer Academic Publishers, Dordrecht. https://doi.org/10.1007/978-1-4757-3389-1
[14]	Wu, T.S. and Chen, L. (2009) Simple Graphs and Commutative Zero-Divisor Semigroups. Algebra Colloquium, 16, 211-218. https://doi.org/10.1142/S1005386709000212
[15]	Wu, T.S. and Lu, D.C. (2006) Zero-Divisor Semigroups and Some Simple Graphs. Communications in Algebra, 34, 3043-3052. https://doi.org/10.1080/00927870600639948