1 Introduction
The zero-divisor graph associated with a commutative ring was first introduced by Beck [Reference Beck2], with the goal of studying graph colouring. Later, Anderson and Livingston [Reference Anderson and Livingstone1] modified the definition so that the vertex set consists only of the nonzero zero-divisors of the ring. This construction was further extended to the context of semigroups and posets in [Reference DeMeyer and DeMeyer4–Reference Joshi and Khiste6].
In a graph G, two distinct vertices a and b are called orthogonal, denoted
$a\perp b$
, if a and b are adjacent and there does not exist a vertex c adjacent to both a and b. Equivalently, adjacent vertices a and b are orthogonal if the edge
$a - b$
is not an edge of any triangle (3-cycle). A graph G is called complemented if for every vertex a, there exists a vertex b such that
$a\perp b$
. A graph G is called uniquely complemented if G is complemented and has the property that if
$a, b, c$
are distinct vertices with
$a\perp b$
and
$a\perp c$
, then
$N(b) = N(c)$
, where
$N(x)$
denotes the neighbourhood of the vertex x. This graph-theoretic property has been studied in the context of the zero-divisor graph associated with a commutative ring (see [Reference LaGrange7]).
Throughout the paper, S denotes a finite commutative semigroup with
$0$
. The set of zero-divisors of S, denoted by
$Z(S)$
, forms an ideal in S. The zero-divisor graph associated with S, denoted by
$G(S)$
, is the graph whose vertices are given by the nonzero zero-divisors, and two distinct vertices a and b are adjacent when
$ab = 0$
. A clique in a graph G is a sub-graph of G where every pair of distinct vertices in the sub-graph are adjacent. The clique number of a graph G is the number of vertices in a maximal clique in G and is denoted by
$\omega (G)$
.
Define an equivalence relation
$\sim $
on the vertex set
$V(G)$
of a graph G by
$a\sim b$
if and only if
$N(a) = N(b)$
. Denote the equivalence class of
$a\in V(G)$
by
$[a]$
. The reduced graph of G, denoted
$G_r$
, is the graph whose vertex set is the set of equivalence classes under the relation
$\sim $
, where two distinct vertices
$[a]$
,
$[b]$
in the vertex set of
$G_r$
are adjacent if and only if vertices a and b are adjacent in the graph G (see [Reference Bender, Cappaert, DeCoste and DeMeyer3]).
Let
$\mathcal {P}(n)$
denote the semigroup consisting of the power set of an n-element set, equipped with the operation of intersection.
In [Reference Bender, Cappaert, DeCoste and DeMeyer3], Bender et al. mentioned that every known example of a zero-divisor graph
$G(S)$
, for finite S, which is complemented and has the clique number
$n \geq 3$
, has reduced graph isomorphic to
$G(\mathcal {P}(n))$
and is also a uniquely complemented graph. The case where the order of S is infinite is open. They posed the following conjectures.
Conjecture 1.1. If
$G(S)$
is a complemented zero-divisor graph with the clique number
$n \geq 3$
, then
$G(S)$
has the reduced graph
$G_r$
which is isomorphic to
$G(\mathcal {P}(n))$
.
Conjecture 1.2. If
$G(S)$
is a complemented zero-divisor graph with the clique number
$3$
or greater, then
$G(S)$
is uniquely complemented.
To settle these conjectures, we explored the underlying structures of complemented zero-divisor graphs in commutative semigroups with zero.
2 Counterexample
Consider the set
$S=\mathcal {P}(3)\times \mathbb {Z}_4=\{(X,\overline {a}) \mid X \in \mathcal {P}(3),~\overline {a} \in \mathbb {Z}_4 \}$
. Clearly, S is a nonempty set, as
$(\emptyset ,\overline {0}) \in S$
. We define a binary operation
$*$
on the set S such that
$(X,\overline {a}) * (Y,\overline {b})=(X \cap Y,~~\overline {a}\times _4\overline {b})$
for
$(X,\overline {a}), (Y,\overline {b}) \in S$
. For simplicity, we denote the binary operation
$\times _4$
on
$\mathbb {Z}_4$
by ‘
$\cdot $
’.
Since
$(\mathcal {P}(3),\cap )$
and
$ (\mathbb {Z}_4,\cdot )$
are both commutative semigroups with zero elements, we can easily prove that
$(S,*)$
is a commutative semigroup with zero element
$(\emptyset , \overline {0})$
.
Observe that
$$ \begin{align*} V(G(S))=\{(X,\overline {a}) \in S \setminus (\emptyset ,\overline {0}) \mid (X,\overline {a})*(Y,\overline {b})=(\emptyset ,\overline {0}) \ \mathrm{for\ some}\ (Y,\overline {b}) \in S \setminus \{(\emptyset ,\overline {0})\}\}. \end{align*} $$
Clearly,
$V(G(S)) \neq \emptyset $
, since
$(\emptyset , \overline {1})*(\{123\}, \overline {0})=(\emptyset , \overline {0})$
. Further, we can easily prove that
$V(G(S))=S\setminus \{(\emptyset , \overline {0}), (\{123\},\overline {1}), (\{123\},\overline {3})\}$
.
First, we claim that the zero-divisor graph
$G(S)$
is complemented.
Let
$(X,\overline {a}) \in V(G(S))$
be any element. Thus,
$(X,\overline {a})\neq (\emptyset , \overline {0})$
and there exists
$(Y,\overline {b}) \neq (\emptyset , \overline {0})$
such that
$(X,\overline {a})*(Y,\overline {b})= (\emptyset , \overline {0}).$
Therefore,
$X \cap Y=\emptyset $
and
$\overline {a}\cdot \overline {b}=\overline {0}$
. Since
$(X,\overline {a}) \neq (\emptyset ,\overline {0})$
, we have
$X \neq \emptyset ~~ \text {or} ~~ \overline {a} \neq \overline {0}$
. Thus, we have the following cases.
Case (I):
$X =\emptyset $
and
$\overline {a} \in \{\overline {1},\overline {2},\overline {3}\}$
. Then,
$(X,\overline {a})\in \{(\emptyset ,\overline {1}), (\emptyset ,\overline {2}), (\emptyset ,\overline {3})\}$
. It is easy to observe that
$(X,\overline {a})\perp (\{1,2,3\},\overline {0})$
.
Case (II):
$X \neq \emptyset $
and
$\overline {a}=\{\overline {0}\}$
. Clearly, one can see that
$(X,\overline {0}) \perp (Y, \overline {b})$
, where
$(Y, \overline {b}) \in \{ (\{1,2,3\}\setminus X,\; \overline {1}), (\{1,2,3\}\setminus X,\; \overline {2}), (\{1,2,3\}\setminus X, \;\overline {3})\}$
.
Case (III):
$X \neq \emptyset $
and
$\overline {a} \in \{\overline {1},\overline {2},\overline {3}\}$
. Then,
$ (X, \overline {a})\perp (\{1,2,3\}\setminus X,\overline {0})$
for any
${X\subsetneqq \{1,2,3\}}$
. Further,
$(\{1,2,3\}, \overline {2}) \perp (\emptyset , \overline {2})$
.
Thus, in any case, any element
$(X,\overline {a})\in V(G(S))$
has a complement in
$G(S)$
. Therefore,
$G(S)$
is a complemented graph. Clearly,
$G(S)$
contains a cycle of length
$3$
, namely,
$(\{1\},\overline {0})-(\{2\},\overline {0})-(\{3\},\overline {0})-(\{1\},\overline {0})$
. This implies that
$\omega {(G(S))} \geq 3$
.
2.1 Counterexample to Conjecture 1.1
For the reduced graph
$G_r(S)$
, first, we determine a neighbourhood
$N((X,\overline {a}))$
for every vertex
$(X,\overline {a})\in V(G(S))$
, as shown now.
-
(A) Let
$X=\emptyset $
and
$\overline {a}\in \{\overline {1},\overline {2}, \overline {3}\}$
.-
(a)
$N((\emptyset ,\overline {1}))=\{(X,\overline {0}) \mid X(\neq \emptyset ) \in \mathcal {P}(3)\}$
$=\{(\{1\},\overline {0}),(\{2\},\overline {0}),(\{3\},\overline {0}),(\{1,2\},\overline {0}),(\{1,3\},\overline {0})\},(\{2,3\},\overline {0}),(\{1,2,3\},\overline {0})\}$
$=N((\emptyset ,\overline {3}))$
. -
(b)
$N((\emptyset ,\overline {2}))=\{(X,\overline {0}),(X,\overline {2}) \mid X(\neq \emptyset ) \in \mathcal {P}(3)\}$
$=\{(\{1\},\overline {0}),(\{2\},\overline {0}),(\{3\},\overline {0}),(\{1,2\},\overline {0}),(\{1,3\},\overline {0})\},(\{2,3\},\overline {0}),(\{1,2,3\},\overline {0}),$
$~~~~~(\{1\},\overline {2}),(\{2\},\overline {2}),(\{3\},\overline {2}),(\{1,2\},\overline {2}),(\{1,3\},\overline {2})\},(\{2,3\},\overline {2}),(\{1,2,3\},\overline {2})\}$
.
-
-
(B) Let
$X\neq \emptyset $
and
$\overline {a}=\overline {0}$
. Then,
$$ \begin{align*} & N((X,\overline{0})) \\ &\quad =\{(\emptyset,\overline{a}),(Y,\overline{b}) \mid \overline{a} \in \{\overline{1},\overline{2},\overline{3}\}, \overline{b} \in \mathbb{Z}_4, Y(\neq \emptyset) \in \mathcal{P}(3) \mbox{ such that } X \cap Y=\emptyset \}. \end{align*} $$
-
(a)
$N((\{1\},\overline {0}))=\{(\emptyset ,\overline {a}),(\{2\},\overline {b}),(\{3\},\overline {b}), (\{2,3\},\overline {b})~|~ \overline {a}\in \{\overline {1},\overline {2}, \overline {3}\} ~\text {and}~ \overline {b}\in \mathbb {Z}_4\}$
. -
(b)
$N((\{2\},\overline {0}))=\{(\emptyset ,\overline {a}),(\{1\},\overline {b}),(\{3\},\overline {b}), (\{1,3\},\overline {b})~|~ \overline {a}\in \{\overline {1},\overline {2}, \overline {3}\} ~\text {and}~ \overline {b}\in \mathbb {Z}_4\}$
. -
(c)
$N((\{3\},\overline {0}))=\{(\emptyset ,\overline {a}),(\{1\},\overline {b}),(\{2\},\overline {b}), (\{1,2\},\overline {b})~|~ \overline {a}\in \{\overline {1},\overline {2}, \overline {3}\} ~\text {and}~ \overline {b}\in \mathbb {Z}_4\}$
. -
(d)
$N((\{1,2\},\overline {0}))=\{(\emptyset ,\overline {a}),(\{3\},\overline {b})~|~ \overline {a}\in \{\overline {1},\overline {2}, \overline {3}\} ~\text {and}~ \overline {b}\in \mathbb {Z}_4\}$
. -
(e)
$N((\{1,3\},\overline {0}))=\{(\emptyset ,\overline {a}),(\{2\},\overline {b})~|~ \overline {a}\in \{\overline {1},\overline {2}, \overline {3}\} ~\text {and}~ \overline {b}\in \mathbb {Z}_4\}$
. -
(f)
$N((\{2,3\},\overline {0}))=\{(\emptyset ,\overline {a}),(\{1\},\overline {b})~|~ \overline {a}\in \{\overline {1},\overline {2}, \overline {3}\} ~\text {and}~ \overline {b}\in \mathbb {Z}_4\}$
. -
(g)
$N((\{1,2,3\},\overline {0}))=\{(\emptyset ,\overline {a})~|~ \overline {a}\in \{\overline {1},\overline {2}, \overline {3}\}\}$
.
Clearly, all the neighbourhoods
$N((\{1\},\overline {0}))$
,
$ N((\{2\},\overline {0}))$
,
$ N((\{3\},\overline {0}))$
,
$ N((\{1,2\},\overline {0}))$
,
$ N((\{2,3\},\overline {0}))$
and
$ N((\{1,3\},\overline {0}))$
are distinct. -
-
(C) Let
$X\neq \emptyset $
and
$\overline {a}\in \{\overline {1}, \overline {3}\}$
. Then,
$$ \begin{align*}N((X,\overline{a}))=\{(Y,\overline{0}) \mid Y (\neq \emptyset) \in \mathcal{P}(3) \text{ such that } X \cap Y=\emptyset\}.\end{align*} $$
-
(a)
$N((\{1\},\overline {a}))=\{(\{2\},\overline {0}),(\{3\},\overline {0}),(\{2,3\},\overline {0})\}$
. -
(b)
$N((\{2\},\overline {a}))=\{(\{1\},\overline {0}),(\{3\},\overline {0}),(\{1,3\},\overline {0})\}$
. -
(c)
$N((\{3\},\overline {a}))=\{(\{1\},\overline {0}),(\{2\},\overline {0}),(\{1,2\},\overline {0})\}$
. -
(d)
$N((\{1,2\},\overline {a}))=\{(\{3\},\overline {0})\}$
. -
(e)
$N((\{1,3\},\overline {a}))=\{(\{2\},\overline {0})\}$
. -
(f)
$N((\{2,3\},\overline {a}))=\{(\{1\},\overline {0})\}$
.
Clearly, all the neighbourhoods
$N((\{1\},\overline {a})) $
,
$ N((\{2\},\overline {a}))$
,
$ N((\{3\},\overline {a}))$
,
$ N((\{1,2\},\overline {a})) $
,
$ N((\{1,3\},\overline {a})) $
and
$ N((\{2,3\},\overline {a}))$
are distinct. -
-
(D) Let
$X \neq \emptyset $
and
$\overline {a}=\overline {2}$
. Then,
$$ \begin{align*}N((X,\overline{2}))=\{(\emptyset,\overline{2}),(Y,\overline{a}) \mid Y (\neq \emptyset) \in \mathcal{P}(3) \text{ such that } X \cap Y=\emptyset \text{ and } \overline{a}\in \{\overline{0}, \overline{2}\}\}.\end{align*} $$
-
(a)
$N((\{1\},\overline {2}))=\{(\emptyset ,\overline {2}),(\{2\},\overline {a}),(\{3\},\overline {a}),(\{2,3\},\overline {a})~|~\overline {a}\in \{\overline {0}, \overline {2}\}\}$
. -
(b)
$N((\{2\},\overline {2}))=\{(\emptyset ,\overline {2}),(\{1\},\overline {a}),(\{3\},\overline {a}),(\{1,3\},\overline {a})~|~\overline {a}\in \{\overline {0}, \overline {2}\}\}$
. -
(c)
$N((\{3\},\overline {2}))=\{(\emptyset ,\overline {2}),(\{1\},\overline {a}),(\{2\},\overline {a}),(\{1,2\},\overline {a})~|~\overline {a}\in \{\overline {0}, \overline {2}\}\}$
. -
(d)
$N((\{1,2\},\overline {2}))=\{(\emptyset ,\overline {2}),(\{3\},\overline {a})~|~\overline {a}\in \{\overline {0}, \overline {2}\}\}$
. -
(e)
$N((\{1,3\},\overline {2}))=\{(\emptyset ,\overline {2}),(\{2\},\overline {a})~|~\overline {a}\in \{\overline {0}, \overline {2}\}\}$
. -
(f)
$N((\{2,3\},\overline {2}))=\{(\emptyset ,\overline {2}),(\{1\},\overline {a})~|~\overline {a}\in \{\overline {0}, \overline {2}\}\}$
. -
(g)
$N((\{1,2,3\},\overline {2}))=\{(\emptyset ,\overline {2})\}$
.
Clearly, all the neighbourhoods
$N((\{1\},\overline {2}))$
,
$ N((\{2\},\overline {2})) $
,
$ N((\{3\},\overline {2}))$
,
$ N((\{1,2\},\overline {2})) $
,
$ N((\{1,3\},\overline {2}))$
,
$ N((\{2,3\},\overline {2}))$
and
$ N((\{1,2,3\},\overline {2}))$
are distinct. -
It follows that
$[(X, \overline {1})]=[(X, \overline {3})]$
and
$$ \begin{align*}V(G_r)=\{[(\emptyset,\overline{2})], [(X,\overline{a})], [(Y,\overline{1})] \mid X(\neq \emptyset)\in \mathcal{P}(3), Y\in \mathcal{P}(3)\setminus \{1,2,3\} \text{ and } \overline{a}\in \{\overline{0},\overline{2}\}\}.\end{align*} $$
Therefore,
$|V(G_r(S))|=22$
.
If we assume that the reduced graph
$G_r(S)$
is isomorphic to the graph
$G(\mathcal {P}(n))$
, then we have
$22=|V(G_r(S))|=|V(G(\mathcal {P}(n)))|=2^n-2$
. This implies that
$2^n=24$
, which is a contradiction to the fact that
$n \in \mathbb {N}$
. Therefore,
$G_r (S)$
is not isomorphic to the graph
$G(\mathcal {P}(n))$
for any
$n \in \mathbb {N}$
.
Thus, Conjuncture 1.1 fails.
2.2 Counterexample to Conjecture 1.2
We now claim that
$G(S)$
is not a uniquely complemented graph.
Let
$u = (\emptyset , \overline {2})$
,
$v = (\{1,2,3\}, \overline {0})$
and
$w = (\{1,2,3\}, \overline {2})$
be elements of
$V(G(S))$
. Observe that
$ u * v = (\emptyset , \overline {0})$
and hence u is adjacent to v in
$G(S)$
. Suppose there exists an element
$t = (X, \overline {a}) \in V(G(S))$
, with
$t \neq u$
and
$t \neq v$
, such that t is adjacent to both u and v, that is,
$t * u = t * v = (\emptyset , \overline {0}).$
This implies
$X = \emptyset $
and
$\overline {a} \in \{\overline {0}, \overline {2} \}$
.
If
$\overline {a} = \overline {0}$
, then
$t = (\emptyset , \overline {0})$
, which is not a vertex of
$G(S)$
, since this element is the zero element of the semigroup and thus excluded from the vertex set.
If
$\overline {a} = \overline {2}$
, then
$t = (\emptyset , \overline {2}) = u$
, which contradicts the assumption
$t \neq u$
.
Therefore, no such t exists, and the edge u–v is not part of a 3-cycle. Thus,
$u \perp v$
in
$G(S)$
. Similarly, it can be shown that
$u \perp w$
in
$G(S)$
.
Next, we examine the neighbourhoods of v and w. Clearly,
$$ \begin{align*}N(v) = \{ (\emptyset, \overline{1}), (\emptyset, \overline{2}), (\emptyset, \overline{3}) \}, \quad N(w) = \{ (\emptyset, \overline{2}) \}.\end{align*} $$
Since
$N(v) \neq N(w)$
, it follows that
$G(S)$
is not a uniquely complemented graph.
Therefore, Conjecture 1.2 fails.
Acknowledgement
The authors would like to thank the referee for suggestions that improved the presentation of the paper.
