AN IDEAL THEORETIC APPROACH TO COMPLETE PARTITE ZERO-DIVISOR GRAPHS OF POSETS

M. ALIZADEH, H. R. MAIMANI, M. R. POURNAKI, AND S. YASSEMI

Abstract. In this paper, we characterize complete partite zero-divisor graphs of posets via the ideals of the posets. In particular, for complete bipartite zero-divisor graphs, we give a characterization based on the prime ideals of the posets.

1. Introduction

Algebraic combinatorics is an area of mathematics that employs methods of abstract algebra in various combinatorial contexts and vice versa. Associating a graph to an algebraic structure is a research subject in this area and has attracted considerable attention. In fact, the research in this subject aims at exposing the relationship between algebra and graph theory and at advancing the application of one to the other. The story goes back to a paper of Beck [3] in 1988, where he introduced the idea of a zero-divisor graph of a commutative ring R with identity. He defined Γ_{0}(R) to be the graph whose vertices are elements of R and in which two vertices x and y are adjacent if and only if xy = 0. He was mostly concerned with coloring of Γ_{0}(R). Let χ(R) and ω(R) denote the chromatic number and the clique number of Γ_{0}(R), respectively. Beck conjectured that χ(R) = ω(R). Such graphs are called weakly perfect graphs. This investigation of coloring of a commutative ring was then continued by Anderson and Naseer in [1]. They gave a counterexample for the above conjecture of Beck. A different method of associating a zero-divisor graph to a commutative ring R was proposed by Anderson and Livingston in [2]. They believed that this better illustrated the zero-divisor structure of the ring. They defined Γ(R) to be the graph whose vertices are nonzero zero-divisors of R and in which two vertices x and y are adjacent if and only if xy = 0. This graph is defined slightly different from the graph introduced by Beck who took the set of vertices to be the whole of R.

In the past decade, many authors have studied zero-divisor graphs of rings or other graphs associated to the other algebraic structures. For instance, Nimbhorkar, Wasadikar, and DeMeyer [8] have shown that Beck’s conjecture holds true for commutative semigroups with zero in which each element is idempotent. These semigroups are called meet-semilattices. Recently, Halaš and Jukl [6] introduced the zero-divisor graphs of posets and gave an affirmative answer to Beck’s question. The study of the zero-divisor graphs of posets was then continued by Xue and Liu in [10]. More recently, a different method of associating a zero-divisor graph to a poset P was proposed by Lu and Wu in [7]. The graph defined by them is slightly different from the one defined in [6, 10], where the vertex-set of the graph consists of all the elements of P. The vertex-set of the graph defined in [7] consists of all nonzero zero-divisors of P.

2000 Mathematics Subject Classification. Primary: 06A07, 06A11; Secondary: 05C70.

Key words and phrases. Poset, Zero-divisor graph of a poset, Complete partite graph, Ideal of a poset, Prime ideal of a poset, Generalized tree.

The research of M. Alizadeh was in part supported by a grant from the University of Tehran. The research of H. R. Maimani, M. R. Pournaki, and S. Yassemi was in part supported by a grant from IPM (No. 90050214, No. 91130115, and No. 91130214).

In this paper, we deal with zero-divisor graphs of posets based on the terminology of [7]. We characterize complete partite zero-divisor graphs of posets via the ideals of the posets. In particular, for complete bipartite zero-divisor graphs, we give a characterization based on the prime ideals of the posets.

2. Preliminaries

In this section, for convenience of the reader, we recall some definitions and notations concerning graphs and posets for later use. For undefined terms and concepts, the reader is referred to [4, 5].

2.1. Some notions from graphs. Throughout the paper by a graph we mean an undirected graph without loops, multiple edges, or isolated vertices. For a graph G, let V (G) denote the set of vertices. For a given integer k, k ≥ 2, a k-partite graph is one whose vertex-set is partitioned into k disjoint nonempty subsets in such a way that the two end vertices for each edge lie in distinct partitions. Among k-partite graphs, a complete k-partite graph is one in which each vertex is joined to every vertex that is not in the same partition. We do not emphasize k and usually write “complete partite graph” instead of “complete k-partite graph”. The 2-partite graph is called bipartite graph and the complete 2-partite graph is called the complete bipartite graph.

2.2. Some notions from posets. Let P be a nonempty set. A binary relation ≤ on P is called a partial order on P if ≤ is reflexive, antisymmetric, and transitive. For x, y ∈ P, we write y < x if y ≤ x and y ≠ x. A set that is equipped with a partial order is called a partially ordered set or a poset, briefly. If P is a poset, then it can be represented by a digraph, called Hasse diagram of the poset P, whose vertices are elements of P and an edge from y to x is present if y < x and there is no z ∈ P such that y < z and z < x. If y < x, then x is drawn higher than y and so the direction of the edges is never indicated in a such diagram.

Let P be a poset and let Q be a nonempty subset of P. If there exists y ∈ Q such that y ≤ x for every x ∈ Q, then y is called the minimum element of Q. The minimum element, if exists, is unique because of the antisymmetry of the partial order. An element x ∈ Q is called a minimal element of Q if y ∈ Q and y ≤ x implies that y = x. We denote the set of minimal elements of Q by Min(Q).

Let P be a poset with minimum element 0. We denote P \ {0} by P^{×}. For every x, y ∈ P, denote L(x, y) = {z ∈ P | z ≤ x and z ≤ y}. An element x ∈ P is called a zero-divisor of P if there exists y ∈ P^{×} such that L(x, y) = {0}. We denote the set of zero-divisors of P by Z(P) and we consider Z(P)^{×} := Z(P) \ {0}. By an ideal of P we mean a nonempty subset I of P such that x ∈ I and y ≤ x implies that y ∈ I. We say that I is proper if I ≠ P. For x ∈ P, consider (x] := {y ∈ P | y ≤ x}. It is easy to see that (x] is an ideal of P, which is called the cyclic ideal of P generated by x. Also, P is called generalized tree if for every x ∈ P and for every x_{1}, x_{2} ∈ (x], either x_{1} ≤ x_{2} or x_{2} ≤ x_{1}. For x ∈ P, the annihilator of x, denoted by Ann(x), is defined to be {y ∈ P | L(x, y) = {0}}. It is easy to see that Ann(x) is an ideal of P. A proper ideal 𝔭 of P is called a prime ideal of P if for every x, y ∈ P, L(x, y) ⊆ 𝔭 implies that either x ∈ 𝔭 or y ∈ 𝔭. We say that a prime ideal 𝔭 of P is an associated prime ideal of P if there exists x ∈ P such that 𝔭 = Ann(x). We denote the set of all associated prime ideals of P by Ass(P).

2.3. Zero-divisor graphs of posets: What we deal with in this paper. Throughout the paper by a poset we mean a nontrivial poset with minimum element 0. Let P be a poset. The zero-divisor graph of P, denoted by Γ(P), is the graph obtained by setting all the elements of Z(P)^{×} to be the vertices and defining distinct vertices x and y to be adjacent if and only if L(x, y) = {0}.

3. The results

In this section, we characterize complete partite zero-divisor graphs of posets via the ideals of the posets. We start with complete bipartite graphs, as they are much easier to handle. In this case, the characterization is based on prime ideals of the posets (see Theorem 3.2). In order to do this, we need the following proposition. Because this proposition is an analogue for a well-known result in commutative ring theory (see, for example, [9, Proposition 8.19 and Remark 8.20]), we state it in a more general form than we will need.

Proposition 3.1. Let P be a poset. Let 𝔭_{1}, …, 𝔭_{k} be prime ideals of P such that ⋂_{i=1}^{k} 𝔭_{i} = {0}, and for every j with 1 ≤ j ≤ k we have

⋂_{\begin{matrix}i = 1 \\ i ≠ j \end{matrix}}^{k} 𝔭_{i} ≠ \{0\}.

Then for every j with 1 ≤ j ≤ k we have 𝔭_{j} ∈ Ass(P). Moreover, Z(P) = ⋃_{i=1}^{k} 𝔭_{i}.

Proof. Let 1 ≤ j ≤ k be given. By the assumption, there exists a nonzero element x such that

x ∈ ⋂_{\begin{matrix}i = 1 \\ i ≠ j \end{matrix}}^{k} 𝔭_{i}.

We claim that Ann(x) = 𝔭_{j}. In order to prove the claim, first let y ∈ Ann(x) be given. Therefore, we have L(x, y) = {0} ⊆ 𝔭_{j}. Since x ∉ 𝔭_{j} and 𝔭_{j} is a prime ideal of P, we conclude that y ∈ 𝔭_{j}. Thus we have Ann(x) ⊆ 𝔭_{j}. Now, let y ∈ 𝔭_{j} be given. For every z ∈ L(x, y), we have z ≤ x and z ≤ y. Since x belongs to the ideal

⋂_{\begin{matrix}i = 1 \\ i ≠ j \end{matrix}}^{k} 𝔭_{i},

and z ≤ x, we conclude that

z ∈ ⋂_{\begin{matrix}i = 1 \\ i ≠ j \end{matrix}}^{k} 𝔭_{i}.

On the other hand, y belongs to the ideal 𝔭_{j} and z ≤ y, so we have z ∈ 𝔭_{j}. Thus

z ∈ ( ⋂_{\begin{matrix}i = 1 \\ i ≠ j \end{matrix}}^{k} 𝔭_{i}) ∩ 𝔭_{j} = ⋂_{i=1}^{k} 𝔭_{i} = \{0\},

and so z = 0. This implies that L(x, y) = {0}, hence y ∈ Ann(x). Thus we have 𝔭_{j} ⊆ Ann(x). Therefore, the claim holds and we have Ann(x) = 𝔭_{j}, which means that 𝔭_{j} ∈ Ass(P), as required.

We now prove the second part of the proposition. By the first part, for every i with 1 ≤ i ≤ k, there exists x_{i} ∈ P such that 𝔭_{i} = Ann(x_{i}). Therefore, we have ⋃_{i=1}^{k} 𝔭_{i} = ⋃_{i=1}^{k} Ann(x_{i}) ⊆ Z(P). Now, let x ∈ Z(P) be given. Then there exists y ∈ P^{×} such that L(x, y) = {0}. Since y ∈ P^{×}, by the assumption, there exists t with 1 ≤ t ≤ k such that y ∉ 𝔭_{t}. But L(x, y) = {0} ⊆ 𝔭_{t} and 𝔭_{t} is prime, therefore we conclude that x ∈ 𝔭_{t} ⊆ ⋃_{i=1}^{k} 𝔭_{i}. Thus Z(P) ⊆ ⋃_{i=1}^{k} 𝔭_{i}. Therefore, we prove that Z(P) = ⋃_{i=1}^{k} 𝔭_{i}, as required. □

The following theorem gives us a characterization of complete bipartite zero-divisor graphs of posets.

Theorem 3.2. Let P be a poset. Then the following statements are equivalent: (a) There exist nonzero prime ideals 𝔭_{1} and 𝔭_{2} of P such that 𝔭_{1} ∩ 𝔭_{2} = {0}.

(b) The zero-divisor graph Γ(P) is a complete bipartite graph.

(c) The zero-divisor graph Γ(P) is a bipartite graph.

Proof. (a) ⟹ (b): We consider V_{1} := 𝔭_{1} \ {0} and V_{2} := 𝔭_{2} \ {0} and we show that the zero-divisor graph Γ(P) is complete bipartite with partite sets V_{1} and V_{2}. In order to do this, note that by the assumption, V_{1} ≠ ∅, V_{2} ≠ ∅, and we have V_{1} ∩ V_{2} = ∅. Also, by Proposition 3.1, we have V (Γ(P)) = Z(P)^{×} = V_{1} ∪ V_{2}.

Let x, y ∈ V_{1} be given. If x and y are adjacent, then L(x, y) = {0} and so L(x, y) ⊆ 𝔭_{2}. Since 𝔭_{2} is prime, either x ∈ 𝔭_{2} or y ∈ 𝔭_{2}. This implies that either x ∈ V_{2} or y ∈ V_{2}, which is a contradiction. Therefore, no elements of V_{1} are adjacent. Similarly, we may prove that no elements of V_{2} are adjacent.

Now let x ∈ V_{1} and let y ∈ V_{2} be given. Therefore, x ∈ 𝔭_{1} and y ∈ 𝔭_{2}. Let z ∈ L(x, y) be given. Then z ≤ x and z ≤ y. Since 𝔭_{1} and 𝔭_{2} are ideals of P, we conclude that z ∈ 𝔭_{1} ∩ 𝔭_{2} = {0} and so z = 0. Therefore L(x, y) = {0}, which implies that x and y are adjacent. Thus every element of V_{1} is adjacent to every element of V_{2}.

This implies that Γ(P) is a complete bipartite graph, as required.

(b) ⟹ (c): It is trivial.

(c) ⟹ (a): Let V_{1} and V_{2} be the partite sets of the bipartite graph Γ(P) and consider 𝔭_{1} = V_{1} ∪ {0} and 𝔭_{2} = V_{2} ∪ {0}. We show that 𝔭_{1} and 𝔭_{2} are the requested prime ideals. It is easy to see that 𝔭_{1} and 𝔭_{2} are nonzero and we have 𝔭_{1} ∩ 𝔭_{2} = {0}.

We show that 𝔭_{1} is an ideal of P. In order to do this, let x and y be elements of P^{×} with y ∈ 𝔭_{1} and suppose that x ≤ y. We show that x ∈ 𝔭_{1}. Since y ∈ 𝔭_{1}, we have y ∈ V_{1}. Therefore, y ∈ Z(P)^{×} and thus there exists z ∈ P^{×} such that L(y, z) = {0}. Thus y and z are adjacent and so z ∈ V_{2}. Since L(x, z) ⊆ L(y, z), we conclude that L(x, z) = {0}. Thus x is adjacent to z which implies that x ∈ V_{1}. Therefore x ∈ 𝔭_{1}, which shows that 𝔭_{1} is an ideal of P. Similarly, we may prove that 𝔭_{2} is an ideal of P.

Now, we prove that the proper ideal 𝔭_{1} is prime. In order to do this, suppose that x and y are elements of P^{×} with L(x, y) ⊆ 𝔭_{1}. We show that x ∈ 𝔭_{1} or y ∈ 𝔭_{1}. There are two possibilities: either L(x, y) = {0} or L(x, y) ≠ {0}.

First, suppose that L(x, y) = {0}. Suppose, on the contrary, that x, y ∉ 𝔭_{1}. Now L(x, y) = {0} implies that x, y ∈ Z(P)^{×} and so x, y ∈ V_{2}. Therefore, x and y are not adjacent and so L(x, y) ≠ {0}, a contradiction. Thus, in this case, we have x ∈ 𝔭_{1} or y ∈ 𝔭_{1}.

Second, suppose that L(x, y) ≠ {0}. Therefore, there exists a nonzero element t such that t ∈ L(x, y). Thus t ∈ 𝔭_{1} and so t ∈ V_{1}. This implies that t ∈ Z(P)^{×} and thus there exists z ∈ P^{×} such that L(t, z) = {0}. Therefore, t and z are adjacent and so z ∈ V_{2}. Then, one of the following cases occur.

Case 1: L(x, z) = {0}. In this case, x ∈ Z(P)^{×} is adjacent to z ∈ V_{2}. Therefore, x ∈ V_{1} and so x ∈ 𝔭_{1}.

Case 2: L(x, z) ≠ {0}. In this case, there exists a nonzero element u such that u ∈ L(x, z). We claim that L(y, u) = {0}. In order to prove the claim, suppose, on the contrary, that L(y, u) ≠ {0}. Therefore, there exists a nonzero element w such that w ∈ L(y, u). This implies that w ≤ y and w ≤ u. But u ∈ L(x, z), and this implies that u ≤ x and so we conclude that w ≤ x. Thus w ∈ L(x, y) and so w ∈ 𝔭_{1}. We have w ≤ u. On the other hand, u ∈ L(x, z) implies that u ≤ z. Therefore, we have w ≤ z and since z ∈ 𝔭_{2} we conclude that w ∈ 𝔭_{2}. Therefore, we obtain that w ∈ 𝔭_{1} ∩ 𝔭_{2} = {0} and so w = 0, which is a contradiction. Therefore, the claim holds and we have L(y, u) = {0}. Since u ≤ z, we conclude that u ∈ V_{2}. By the claim, L(y, u) = {0}, and so y and u are adjacent. This implies that y ∈ V_{1} and so y ∈ 𝔭_{1}.

Therefore, 𝔭_{1} is a prime ideal of P. Similarly, we may prove that the proper ideal 𝔭_{2} is a prime ideal of P. □

Let P be a poset. By Theorem 3.2, the zero-divisor graph Γ(P) is k-partite if and only if it is complete k-partite, provided k = 2. The following example shows that this is not the case for k > 2.

Example 3.3. Let 𝕀 denote the closed unit interval [0, 1] and suppose that x and y are two real numbers such that x, y ∉ 𝕀. Let P = 𝕀 ∪ {x, y} and define ≤ by

{(a, b) | a, b ∈ 𝕀 and a is less than or equal to b} ∪ {(x, x), (y, y), (0, x), (0, y), (x, 1)}.

It is easy to see that ≤ is a partial order on P and so P is a poset. The Hasse diagram of P is displayed in Fig. 1. Here, the zero-divisor graph Γ(P) is 3-partite with partite sets 𝕀 \ {0}, {x}, and {y}, while it is not complete 3-partite because x is not adjacent to 1.

[figure: 0; x; y; 1]

Figure 1. The Hasse diagram of the poset P.

Now it is natural to ask what happens when the graph is complete k-partite, k > 2. In the following theorem, we characterize these graphs in terms of the ideals of the posets, however the theorem works also for k = 2.

Theorem 3.4. Let P be a poset and k ≥ 2. Consider the following statements: (a) The zero-divisor graph Γ(P) is a complete k-partite graph.

(b) |Min(P^{×})| ≤ k and for every x ∈ Z(P)^{×} we have |(x] ∩ Min(P^{×})| ≤ 1. Then (a) implies (b). Moreover, if equality holds in each parts of (b), then (b) also implies (a).

Proof. (a) ⟹ (b): We first show that |Min(P^{×})| ≤ k. Suppose that Min(P^{×}) has at least two elements, otherwise there is nothing to prove. If x and y are distinct elements of Min(P^{×}), then L(x, y) = {0}. This implies that x, y ∈ Z(P)^{×} and so x and y are vertices of Γ(P) which are adjacent. By the assumption, Γ(P) is a complete k-partite graph and so x and y belong to the different parts of Γ(P). Since the number of different parts of Γ(P) is equal to k, we conclude that |Min(P^{×})| ≤ k.

For proof of the second part, suppose, on the contrary, that there exists x ∈ Z(P)^{×} such that |(x] ∩ Min(P^{×})| ≥ 2. Therefore, we may choose distinct elements x_{1} and x_{2} in (x] ∩ Min(P^{×}). Since x_{1}, x_{2} ∈ (x], we conclude that x_{1} ≤ x and x_{2} ≤ x. This implies that x_{1} ∈ L(x_{1}, x) and x_{2} ∈ L(x_{2}, x), and therefore, we obtain L(x_{1}, x) ≠ {0} and L(x_{2}, x) ≠ {0}. Thus x_{1} and x_{2} are not adjacent to x. Since Γ(P) is complete k-partite, we conclude that x_{1} and x_{2} are in a same part of Γ(P) and so are not adjacent. This implies that L(x_{1}, x_{2}) ≠ {0}. But x_{1}, x_{2} ∈ Min(P^{×}), and this implies that L(x_{1}, x_{2}) = {0}, a contradiction. Therefore, for every x ∈ Z(P)^{×} we have |(x] ∩ Min(P^{×})| ≤ 1.

Moreover, we assume that |Min(P^{×})| = k and for every x ∈ Z(P)^{×} we have |(x] ∩ Min(P^{×})| = 1. We then prove the other implication.

(b) ⟹ (a): Since |Min(P^{×})| = k, we may let Min(P^{×}) = {x_{1}, …, x_{k}}. For every i with 1 ≤ i ≤ k consider V_{i} = {x ∈ Z(P)^{×} | x_{i} ≤ x}, which is nonempty. We prove that Γ(P) is a complete k-partite graph with partite sets V_{1}, …, V_{k}.

Step 1: Let 1 ≤ i, j ≤ k with i ≠ j be given. If x ∈ V_{i} ∩ V_{j}, then x_{i} ≤ x and x_{j} ≤ x and so x_{i}, x_{j} ∈ (x]. Therefore, we have x_{i}, x_{j} ∈ (x] ∩ Min(P^{×}). Since |(x] ∩ Min(P^{×})| = 1, we conclude that x_{i} = x_{j}, which is a contradiction. Thus for every 1 ≤ i, j ≤ k with i ≠ j we have V_{i} ∩ V_{j} = ∅.

Step 2: Let x ∈ Z(P)^{×} be given. Since |(x] ∩ Min(P^{×})| = 1, there exists i with 1 ≤ i ≤ k such that (x] ∩ Min(P^{×}) = {x_{i}}. This implies that x_{i} ≤ x and so x ∈ V_{i}. Therefore, we conclude that V (Γ(P)) = Z(P)^{×} = V_{1} ∪ ⋯ ∪ V_{k}.

Step 3: Let 1 ≤ i ≤ k be given. If x, y ∈ V_{i}, then x_{i} ≤ x and x_{i} ≤ y. Therefore, x_{i} ∈ L(x, y) and so L(x, y) ≠ {0}. This implies that x and y are not adjacent.

Step 4: Let 1 ≤ i, j ≤ k with i ≠ j be given and suppose that x ∈ V_{i} and y ∈ V_{j}. Therefore, x_{i} ≤ x and x_{j} ≤ y and since |(x] ∩ Min(P^{×})| = 1 and |(y] ∩ Min(P^{×})| = 1, we conclude that (x] ∩ Min(P^{×}) = {x_{i}} and (y] ∩ Min(P^{×}) = {x_{j}}. We claim that L(x, y) = {0}. If L(x, y) ≠ {0}, then there exists z ∈ P^{×} such that z ∈ L(x, y). Therefore, z ≤ x and z ≤ y. On the other hand, since z ∈ Z(P)^{×}, |(z] ∩ Min(P^{×})| = 1 and so there exists t with 1 ≤ t ≤ k such that (z] ∩ Min(P^{×}) = {x_{t}} which implies that x_{t} ≤ z. Therefore, we have x_{t} ≤ x and x_{t} ≤ y. This implies that x_{t} ∈ (x] ∩ Min(P^{×}) = {x_{i}} and x_{t} ∈ (y] ∩ Min(P^{×}) = {x_{j}}. Thus x_{i} = x_{t} = x_{j}, which is a contradiction. Therefore, L(x, y) = {0}. This implies that x and y are adjacent.

The above steps show that Γ(P) is a complete k-partite graph with partite sets V_{1}, …, V_{k}, as required. □

Remark 3.5. Note that the assertion “equality holds in each parts of (b)” for the implication (b) ⟹ (a) in Theorem 3.4 is necessary, as Example 3.3 shows. In fact, in this example, |Min(P^{×})| = 2, for every z ∈ Z(P)^{×} we have |(z] ∩ Min(P^{×})| ≤ 1 and, for example, |(1/2]∩Min(P^{×})| = 0. Therefore, the condition (b) holds true, while the above-mentioned extra assertion does not hold. Since the zero-divisor graph Γ(P) is not complete bipartite, we cannot conclude (a).

In the following theorem, we give a sufficient condition for zero-divisor graphs of posets to be complete k-partite.

Theorem 3.6. Let P be a poset and k ≥ 2. Let |Min(P^{×})| = k and Z(P)^{×} be a generalized tree. If for every x ∈ P^{×}, the set (x] \ {0} has a minimal element, then the zero-divisor graph Γ(P) is a complete k-partite graph. Moreover, if V_{1}, …, V_{k} are partite sets of Γ(P), then for every i with 1 ≤ i ≤ k, the set

𝔭_{i} = ( ⋃_{\begin{matrix}j = 1 \\ j ≠ i \end{matrix}}^{k} V_{j}) ∪ \{0\}

is a prime ideal of P.

Proof. We first prove that Γ(P) is a complete k-partite graph. In order to prove this, by Theorem 3.4, it is enough to show that for every x ∈ Z(P)^{×} we have |(x] ∩ Min(P^{×})| = 1. Suppose, on the contrary, that there exists x ∈ Z(P)^{×} such that |(x] ∩ Min(P^{×})| ≠ 1. Therefore, by the assumption, we have |(x] ∩ Min(P^{×})| ≥ 2 and so we may choose distinct elements x_{1} and x_{2} in (x] ∩ Min(P^{×}). Therefore, x_{1}, x_{2} ∈ (x]. But x ∈ Z(P)^{×}, and by the assumption Z(P)^{×} is a generalized tree, thus we conclude that either x_{1} ≤ x_{2} or x_{2} ≤ x_{1}. Both cases led to a contradiction, because x_{1}, x_{2} ∈ Min(P^{×}). Therefore, for every x ∈ Z(P)^{×} we have |(x] ∩ Min(P^{×})| = 1 and so we conclude the first part of the theorem.

For proof of the second part of the theorem, we first show that 𝔭_{i}, 1 ≤ i ≤ k, is an ideal of P. Let x and y be elements of P^{×} with y ∈ 𝔭_{i} and suppose that x ≤ y. We show that x ∈ 𝔭_{i}. Since y ∈ Z(P)^{×}, there exists z ∈ P^{×} such that L(y, z) = {0}. But L(x, z) ⊆ L(y, z), and so L(x, z) = {0} which implies that x ∈ Z(P)^{×}. Therefore, there exists t with 1 ≤ t ≤ k such that x ∈ V_{t}. Since y ∈ 𝔭_{i}, we conclude that y ∉ V_{i}. Let w ∈ V_{i} be given. Since Γ(P) is a complete k-partite graph, y is adjacent to w. Therefore, we have L(y, w) = {0}, and since L(x, w) ⊆ L(y, w), we conclude that L(x, w) = {0}. Thus x is adjacent to w which implies that x ∉ V_{i}. Therefore, x ∈ 𝔭_{i} which shows that 𝔭_{i} is an ideal of P.

Now, we prove that the proper ideal 𝔭_{i} is prime. In order to do this, suppose that x and y are elements of P^{×} with L(x, y) ⊆ 𝔭_{i}. We show that x ∈ 𝔭_{i} or y ∈ 𝔭_{i}. There are two possibilities: either L(x, y) = {0} or L(x, y) ≠ {0}.

First, suppose that L(x, y) = {0}. Suppose, on the contrary, that x, y ∉ 𝔭_{i}. Now L(x, y) = {0} implies that x, y ∈ Z(P)^{×} and so x, y ∈ V_{i}. Therefore, x and y are not adjacent and so L(x, y) ≠ {0}, a contradiction. Thus, in this case, we have x ∈ 𝔭_{i} or y ∈ 𝔭_{i}.

Second, suppose that L(x, y) ≠ {0}. Therefore, there exists a nonzero element t such that t ∈ L(x, y). Thus t ∈ 𝔭_{i} and so t ∉ V_{i}. Let z ∈ V_{i} be given. Since the graph Γ(P) is complete k-partite, we conclude that t and z are adjacent and so L(t, z) = {0}. Then, one of the following cases occur.

Case 1: L(x, z) = {0}. In this case, x ∈ Z(P)^{×} is adjacent to z ∈ V_{i}. Therefore, x ∉ V_{i} and so x ∈ 𝔭_{i}.

Case 2: L(x, z) ≠ {0}. In this case, there exists a nonzero element u such that u ∈ L(x, z). We claim that L(y, u) = {0}. In order to prove the claim, suppose, on the contrary, that L(y, u) ≠ {0}. Therefore, there exists a nonzero element w such that w ∈ L(y, u). This implies that w ≤ y and w ≤ u. But u ∈ L(x, z), and this implies that u ≤ x and so we conclude that w ≤ x. Thus w ∈ L(x, y) and so w ∈ 𝔭_{i}.

It is easy to see that

⋂_{\begin{matrix}j = 1 \\ j ≠ i \end{matrix}}^{k} 𝔭_{j} = V_{i} ∪ \{0\},

which is, of course, an ideal of P. We have w ≤ u. On the other hand, u ∈ L(x, z) implies that u ≤ z. Therefore, we have w ≤ z and since

z ∈ ⋂_{\begin{matrix}j = 1 \\ j ≠ i \end{matrix}}^{k} 𝔭_{j},

we conclude that

w ∈ ⋂_{\begin{matrix}j = 1 \\ j ≠ i \end{matrix}}^{k} 𝔭_{j}.

All in all, we obtain that w ∈ ⋂_{j=1}^{k} 𝔭_{j} = {0} and so w = 0, which is a contradiction. Therefore, the claim holds and we have L(y, u) = {0}. Since u ≤ z, we conclude that

u ∈ ⋂_{\begin{matrix}j = 1 \\ j ≠ i \end{matrix}}^{k} 𝔭_{j} = V_{i} ∪ \{0\},

and so u ∈ V_{i}. By the claim, L(y, u) = {0}, and so y and u are adjacent. This implies that y ∉ V_{i} and so y ∈ 𝔭_{i}.

Therefore, 𝔭_{i} is a prime ideal of P, as required. □

Note that the converse of Theorem 3.6 is not true, as the following example shows.

Example 3.7. Let P = {0, x_{1}, x_{2}, x_{3}, x_{4}, x_{5}} be a poset for which its Hasse diagram is displayed in Fig. 2. For this poset, the zero-divisor graph Γ(P) is complete bipartite, while the set Z(P)^{×} is not a generalized tree.

[figure: 0; x_{2}; x_{5}; x_{3}; x_{1}; x_{4}]

Figure 2. The Hasse diagram of the poset P.

Acknowledgments

The authors would like to thank the referee for his/her careful reading of the paper and for his/her valuable comments. Also thanks are due to Ashish Kumar Das from North-Eastern Hill University, India, for his useful suggestions which helped in restructuring Theorem 3.4 in the present form.

References

[1] D. D. Anderson, M. Naseer, Beck’s coloring of a commutative ring, J. Algebra 159 (1993), no. 2, 500–514.

[2] D. F. Anderson, P. S. Livingston, The zero-divisor graph of a commutative ring, J. Algebra 217 (1999), no. 2, 434–447.

[3] I. Beck, Coloring of commutative rings, J. Algebra 116 (1988), no. 1, 208–226.

[4] G. Chartrand, O. R. Oellermann, Applied and Algorithmic Graph Theory, McGraw-Hill, Inc., New York, 1993.

[5] B. A. Davey, H. A. Priestley, Introduction to Lattices and Order, Second Edition, Cambridge University Press, New York, 2002.

[6] R. Halaš, M. Jukl, On Beck’s coloring of posets, Discrete Math. 309 (2009), no. 13, 4584–4589.

[7] D. Lu, T. Wu, The zero-divisor graphs of posets and an application to semigroups, Graphs Combin. 26 (2010), no. 6, 793–804.

[8] S. K. Nimbhorkar, M. P. Wasadikar, L. DeMeyer, Coloring of meet-semilattices, Ars Combin. 84 (2007), 97–104.

[9] R. Y. Sharp, Steps in Commutative Algebra, Second Edition, Cambridge University Press, Cambridge, 2000.

[10] Z. Xue, S. Liu, Zero-divisor graphs of partially ordered sets, Appl. Math. Lett. 23 (2010), no. 4, 449–452.

M. Alizadeh, School of Mathematics, Statistics and Computer Science, College of Science, University of Tehran, Tehran, Iran.

E-mail address: malizadeh@khayam.ut.ac.ir

H. R. Maimani, Mathematics Section, Department of Basic Sciences, Shahid Rajaee Teacher Training University, P.O. Box 16785-163, Tehran, Iran, and School of Mathematics, Institute for Research in Fundamental Sciences (IPM), P.O. Box 19395-5746, Tehran, Iran.

E-mail address: maimani@ipm.ir

M. R. Pournaki, Department of Mathematical Sciences, Sharif University of Technology, P.O. Box 11155-9415, Tehran, Iran, and School of Mathematics, Institute for Research in Fundamental Sciences (IPM), P.O. Box 19395-5746, Tehran, Iran.

E-mail address: pournaki@ipm.ir
URL: http://math.ipm.ac.ir/pournaki/

S. Yassemi, School of Mathematics, Statistics and Computer Science, College of Science, University of Tehran, Tehran, Iran, and School of Mathematics, Institute for Research in Fundamental Sciences (IPM), P.O. Box 19395-5746, Tehran, Iran.

E-mail address: yassemi@ipm.ir
URL: http://math.ipm.ac.ir/yassemi/