1. Introduction
Throughout, G is a simple and connected graph. For a vertex x of G, the neighborhood of x is denoted as
, which is the set of all vertices adjacent to x. Denote also
. The cardinality of
is denoted by deg(x). The vertex x is called an end vertex if
, and an isolated vertex if
( [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
is an undirected graph whose vertices are the zero-divisors of
, and with two vertices
adjacent in case
( [2] - [6] ). If
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
were established in [3] [4] [5] among others. For example, it was proved that
is always connected, and the diameter of
is less than or equal to 3. If
contains a cycle, then its core, i.e., the union of the cycles in
, 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
is still a fun problem.
For any adjacent vertices
in
, denote
and let
denote the set of all end vertices adjacent to a. In [12] , we discuss the properties of
satisfies condition (
), here we assume
and consider the following Δ assumed on
(Δ) There exist in G two adjacent vertices
, a vertex
and a vertex z such that
.
In this paper, we study algebraic properties of semigroup S and the graphic structures of
such that the condition (Δ) holds for
. (We can further assume that triangles and rectangles coexist in the core
.) In particular, it is proved that
is an ideal of S. Under some additional conditions, it is proved that
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
. Since S is a finite set, there exist
such that
. Let
, and take k such that
. Then
□
2. Properties of S
Note that, for any
,
, thus for any vertex
,
, and
,we have the following lemma.
Lemma 2.1. Let S be a commutative semigroup with 0,
its zero-divisor graph. For any vertex
, if there exists a vertex
such that
, then
in S.
Proof. As
, there exist vertices
such that
,
and
. If
, then
and thus
. Clearly
. Then
, 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
be a zero-divisor graph of a semigroup S. For a vertex
, let
.
1) If
, then
is a sub-semigroup of S.
2) If b is not an end vertex and
, then
is an ideal of S.
Proof. (1) We only need consider as
. 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
. For all
, we must have
, since otherwise
, a contradiction. This shows that
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
where
. For all
, we have
If
, denote
. Then there exists
such that
. Since
, we have
. Clearly,
. If
, then
, a contradiction. If
, then
, another contradiction. So we must have
. If
, then exists a vertex
such that
. If
, denote
. Then there exists
such that
. As
, we have
and
, and thus
and
. Then
. On the other hand,
, a contradiction. So
, and hence
.
(2) Since
, there exists
such that
for all
. By assumption, b is not an end vertex and thus there exists
such that
. Then
since otherwise,
and it implies
, a contradiction. This completes the proof. □
Remark 2.3. In Proposition 2.2(1), the conclusion can not hold if
.
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
be a semigroup graph satisfying condition (Δ). Then
is an ideal of S, and
is an ideal of S. Furthermore,
1) If both a and b are internal vertices, then
is an ideal of S.
2) If a is an internal vertex, while b is not an internal vertex and
, then
is a sub-semigroup of S.
Proof. Fix some
and let
,
. By assumption
,
, and
. Notice that there is no end vertex in
. By [ [3] , Theorem 2.3] or by [ [5] , Theorem 1(2)],
and it is a disjoint union of four nonempty subsets. By Lemma 2.1. we have
,
, and hence
. Clearly,
,
and
This shows that
is an ideal of S.
For any y in L, there exists a vertex
such that
. Then
while
. Hence
. Furthermore, for any
,
. If
, then it is clear that
whether
or not. Thus
, and hence
For any vertex
in
,
and it has degree greater than one. Hence for any
and any
, there exists a vertex
such that
. Then
and it implies
. Thus
. Finally, by [ [5] , Theorem 4], the core of G together with 0 forms an ideal of S. Thus these arguments show that
is an ideal of S.
1) If both a and b are internal vertices, then
. In this case,
is clearly an ideal of S.
2) Now assume that b is not an internal vertex, and
. Again let
be the set of end vertices adjacent to b. By the above discussion, we already have
. Since
, we have
by Theorem 2.2(1). These facts show that
is a sub-semigroup of S, and it completes the proof. □
Remarks 2.5. In Theorem 2.4, if there is no
such that
, 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
,
, and
. By Theorem 2.4, if G has a corresponding semigroup
, then the subset
must be an ideal of S. If further
, then
is a sub-semigroup of S. Also by [ [7] , Theorem 2.1],
is a sub-semigroup of
, and thus a sub-semigroup of S.
For
,
and
, it is not very hard to construct a semigroup T such that
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
to this table such that
. The multiplication on S is listed in Table 1 and the detailed verification for the associativity is omitted here:
Notice that
is not a sub-semigroup of S since
. Notice also that
is a sub-semigroup of S.
We remark that the construction in Table 1 can be routinely extended for all
,
,
and
, where each of
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
,
,
and
.
Remark 3.2. Consider the graph G in Figure 1 and assume that
,
,
,
.
1) If we add an end vertex w which is adjacent to b, then the resulting graph
has no corresponding zero-divisor semigroup, even if
.
2) If we add a vertex w such that
, then the resulting graph H has no corresponding zero-divisor semigroup, even if
.
Proof. (1) Assume
. We only need consider the case when
. Suppose that
is the zero-divisor graph of a semigroup S with
. By Proposition 2.2(2), we have
and
. Clearly,
, and thus
and
. As
, we have
. That means
and
. We have
and
. Thus
and
by Lemma 2.1. Consider
. We have
, a contradiction. The contradiction shows that
has no corresponding semigroup.
(2) Assume
. We only need consider the case
. Suppose that H is the zero-divisor graph of a semigroup S. We have
. Clearly,
![]()
Table 1. The associative multiplication table of S in Example 3.1.
since
. If
, then we have
and
, which means
. As
, we have
. Then
, a contradiction. Now assume
and consider
.
. We claim
since otherwise,
, a contradiction. In a similar way we prove
. Moreover,
whether
or
. Thus
. As
, we have
, but
. Now consider
. We conclude
since otherwise,
and it implies
, a contradiction. Finally,
implies
, 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.,
, where after taking a c in
(For example, for the graph G in Figure 1,
,
,
. In particular, L consists of end vertices.) By [ [5] , Theorem 1(4)], for each pair
of nonadjacent vertices of G, there is a vertex z with
. 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 Ta that are adjacent to a, end vertices in Tb that are adjacent to b, vertices in B2 that are adjacent to both a and b, and vertices in B1 that are adjacent to one of
and at the same time adjacent to another vertex in B. By Example 3.1, the structure of the induced subgraph on
seems to be complicated. In the following, we will give a complete classification of the semigroup graphs G with
.
First, consider the case
.
Theorem 3.3. Let G be a graph satisfying condition (Δ). Assume further that
. Then G is a semigroup graph if and only if the following conditions hold:
1)
,
and W consists of end vertices, where
.
2) either
or
. (see Figure 2 with
.)
Proof. As
,
. By the previous observations, we need only prove the following two facts.
1) If
and
, then G is a subgraph of Figure 1 with
. (see also Figure 2 with
.) We claim that G is a semigroup graph. In fact, if
, delete the three rows and the three columns involving
and u in Table 1 to obtain an associative multiplication on
. Clearly,
for
,
in Figure 1. Also, the table can be extended for any finite or infinite
and
while
. If
, then we work out a corresponding associative multiplication table listed in Table 2, for
,
,
in Figure 2.
Clearly, the table can be extended for all finite or infinite
,
and
. This completes the proof. □
(2) If both
and
, then we conclude that G is not a semigroup graph.
In fact, in this case, G is a graph in Figure 2, where
,
,
. Assume
,
,
and
. 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
. By Proposition 2.2(2), we have
. Then
, which implies
.
![]()
Figure 2. A class of graph satisfying condition (
) and
.
![]()
Table 2. The associative multiplication table of S for |U| > 0.
Assume
. Then
, and thus
by Lemma 2.1. As
, we have
, thus
. Then
, a contradiction.
So
, and therefore
. We have
and thus
. Then
, 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
,
,
(
,
,
) and V consists of end vertices adjacent to b. Notice that each of
and
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
. We use Theorem 2.4 and list the associative multiplication in Table 3. Clearly, the table can be extended for all finite or infinite
, and
.
This completes the proof.
□
We have three remarks to Example 3.4.
(1) Let
. If we add to G in Figure 3 an end vertex u such that
, then the resulting graph
has no corresponding zero-divisor semigroup.
Proof. (1) Suppose to the contrary that
is the zero-divisor graph of a semigroup P with
. By Proposition 2.2(2), we have
and
. First, we have
and similarly,
. Then
and
since
. On the other hand,
and it implies
. Similarly,
![]()
Figure 3. A class of semigroup graph with B2 = {x1, x2}.
![]()
Table 3. The associative multiplication table of S in Example 3.4.
we have
. Consider
. We have
, a contradiction. This completes the proof. □
(2) Let
. If we add to G in Figure 3 an end vertex y such that
, then the resulting graph
has no corresponding zero-divisor semigroup, whether or not
.
Proof. (2) Assume
, where y is an end vertex adjacent to
. Suppose to the contrary that
is the zero-divisor graph of a semigroup P with
. First,
. Thus
, and hence
. By Proposition 2.2(2), we have
and therefore,
. Thus
. We have
since
. Since
,
and
, it follows that
. Finally,
and by Lemma 2.1, we have
, contradicting
. This completes the proof.
□
(3) Let
and assume
in Figure 3. If further we add to G an edge connecting
and
, then the resulting graph
has no corresponding zero-divisor semigroup.
Proof. Suppose to the contrary that
is the zero-divisor graph of a semigroup P with
. By Lemma 2.1, we have
and similarly,
. Then we have
and
, which means
since
by Lemma 2.1. Similarly, we have
. Clearly, we have
. Then as
for some
, we have
. Finally,
(for some
), 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
:
Theorem 3.5. Let G be a graph satisfying condition (Δ). Assume further
.
(1) If
, then G is a semigroup graph if and only if G is a graph in Figure 3, where
,
and
.
(2) If
, then G is a semigroup graph if and only G is a graph in Figure 1, where
,
,
.
Proof. (1) By Example 3.4, each graph in Figure 3 is a semigroup graph. Clearly,
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
, then assume
, where
. In this case,
in G. If
in G, then there is no end vertex adjacent to
. In this subcase, G is a semigroup graph if and only if
by Example 3.1 and Remark 3.2(1), the case of
. The other subcase is
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
with
for any
? At present, it seems to be a rather difficult question.
Add two end vertices to two vertices of the complete graph Kn to obtain a new graph, and denote the new graph as
. By [ [14] , Theorem 2.1],
has a unique zero-divisor semigroup S such that
for each
. Having Theorem 2.4 in mind, it is natural to consider graphs obtained by adding some caps to
.
Example 3.6. Consider the graph G in Figure 4. The subgraph G1 induced on the vertex subset
is the graph
, i.e., K4 together with two end vertices
. Then G1 has a unique corresponding zero-divisor semigroup
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 G1 a vertex c such that
, then the resulting graph H1 has no corresponding zero-divisor semigroup.
(2) If we add to G1 a vertex d such that
, then the resulting
![]()
Table 4. The associative multiplication table of K4 + 2.
graph H2 has no corresponding zero-divisor semigroup.
(3) If we add to G1 vertices
(
) such that
, 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
.
Proof. (1) Suppose that H1 is the zero-divisor graph of a semigroup S1 with
. Then by Theorem 2.4, S is an ideal of
. Thus we only need check the associative multiplication of S1 based on the table of S already given in Table 4. First, we have
by Proposition 2.2(2). Consider
. Clearly,
, a contradiction. This completes the proof.
(2) Suppose that H2 is the zero-divisor graph of a semigroup
with
. If
, then by Theorem 2.4(2), S is a sub-semigroup of S2. Then
, and it implies
by Table 4, a contradiction.
![]()
Table 5. The associative multiplication table of K4 + 2 with some caps on x1, x2.
In the following we assume
.
By Lemma 2.1, we have
, and thus
. Clearly
and we can have
. (Otherwise,
and we have
, a contradiction.) Then
, and thus
. It means
and
. Clearly
, and thus
,
by Lemma 2.1. Similarly,
and thus
,
. Finally, consider
. We have
, a contradiction. This completes the proof.
(3) Suppose that H is the subgraph of G in Figure 4 induced on the vertex set
. Assume that H is the zero-divisor graph of a semigroup P with
. Clearly, it dose not satisfy the condition of Theorem 2.4. For
, 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 K4 by Kn for any
, 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
and let
be the complete graph Kn together with two end vertices. Add some (finite or infinite) caps to the subgraph Kn 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).