On the inclusion ideal graph of a poset
Let (P,≤) be an atomic partially ordered set (poset, briefly) with a minimum element 0 and 𝕿(P) the set of nontrivial ideals of P. The inclusion ideal graph of P, denoted by Ω(P), is an undirected and simple graph with the vertex set 𝕿(P) and two distinct vertices I, J ∈ 𝕿(P) are adjacent in Ω(P) if...
Gespeichert in:
| Datum: | 2019 |
|---|---|
| Hauptverfasser: | , , |
| Format: | Artikel |
| Sprache: | English |
| Veröffentlicht: |
Інститут прикладної математики і механіки НАН України
2019
|
| Schriftenreihe: | Algebra and Discrete Mathematics |
| Online Zugang: | http://dspace.nbuv.gov.ua/handle/123456789/188437 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | On the inclusion ideal graph of a poset / N. Jahanbakhsh, R. Nikandish, M.J. Nikmehr // Algebra and Discrete Mathematics. — 2019. — Vol. 27, № 2. — С. 269–279. — Бібліогр.: 10 назв. — англ. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-188437 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1884372023-03-02T01:27:34Z On the inclusion ideal graph of a poset Jahanbakhsh, N. Nikandish, R. Nikmehr, M.J. Let (P,≤) be an atomic partially ordered set (poset, briefly) with a minimum element 0 and 𝕿(P) the set of nontrivial ideals of P. The inclusion ideal graph of P, denoted by Ω(P), is an undirected and simple graph with the vertex set 𝕿(P) and two distinct vertices I, J ∈ 𝕿(P) are adjacent in Ω(P) if and only if I ⊂ J or J ⊂ I. We study some connections between the graph theoretic properties of this graph and some algebraic properties of a poset. We prove that Ω(P) is not connected if and only if P = {0, a1, a2}, where a1, a2 are two atoms. Moreover, it is shown that if Ω(P) is connected, then diam(Ω(P)) ≤ 3. Also, we show that if Ω(P) contains a cycle, then girth(Ω(P)) ∈ {3, 6}. Furthermore, all posets based on their diameters and girths of inclusion ideal graphs are characterized. Among other results, all posets whose inclusion ideal graphs are path, cycle and star are characterized. 2019 Article On the inclusion ideal graph of a poset / N. Jahanbakhsh, R. Nikandish, M.J. Nikmehr // Algebra and Discrete Mathematics. — 2019. — Vol. 27, № 2. — С. 269–279. — Бібліогр.: 10 назв. — англ. 1726-3255 2010 MSC: 06A07; 05C25. http://dspace.nbuv.gov.ua/handle/123456789/188437 en Algebra and Discrete Mathematics Інститут прикладної математики і механіки НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
English |
| description |
Let (P,≤) be an atomic partially ordered set (poset, briefly) with a minimum element 0 and 𝕿(P) the set of nontrivial ideals of P. The inclusion ideal graph of P, denoted by Ω(P), is an undirected and simple graph with the vertex set 𝕿(P) and two distinct vertices I, J ∈ 𝕿(P) are adjacent in Ω(P) if and only if I ⊂ J or J ⊂ I. We study some connections between the graph theoretic properties of this graph and some algebraic properties of a poset. We prove that Ω(P) is not connected if and only if P = {0, a1, a2}, where a1, a2 are two atoms. Moreover, it is shown that if Ω(P) is connected, then diam(Ω(P)) ≤ 3. Also, we show that if Ω(P) contains a cycle, then girth(Ω(P)) ∈ {3, 6}. Furthermore, all posets based on their diameters and girths of inclusion ideal graphs are characterized. Among other results, all posets whose inclusion ideal graphs are path, cycle and star are characterized. |
| format |
Article |
| author |
Jahanbakhsh, N. Nikandish, R. Nikmehr, M.J. |
| spellingShingle |
Jahanbakhsh, N. Nikandish, R. Nikmehr, M.J. On the inclusion ideal graph of a poset Algebra and Discrete Mathematics |
| author_facet |
Jahanbakhsh, N. Nikandish, R. Nikmehr, M.J. |
| author_sort |
Jahanbakhsh, N. |
| title |
On the inclusion ideal graph of a poset |
| title_short |
On the inclusion ideal graph of a poset |
| title_full |
On the inclusion ideal graph of a poset |
| title_fullStr |
On the inclusion ideal graph of a poset |
| title_full_unstemmed |
On the inclusion ideal graph of a poset |
| title_sort |
on the inclusion ideal graph of a poset |
| publisher |
Інститут прикладної математики і механіки НАН України |
| publishDate |
2019 |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/188437 |
| citation_txt |
On the inclusion ideal graph of a poset / N. Jahanbakhsh, R. Nikandish, M.J. Nikmehr // Algebra and Discrete Mathematics. — 2019. — Vol. 27, № 2. — С. 269–279. — Бібліогр.: 10 назв. — англ. |
| series |
Algebra and Discrete Mathematics |
| work_keys_str_mv |
AT jahanbakhshn ontheinclusionidealgraphofaposet AT nikandishr ontheinclusionidealgraphofaposet AT nikmehrmj ontheinclusionidealgraphofaposet |
| first_indexed |
2025-07-16T10:28:33Z |
| last_indexed |
2025-07-16T10:28:33Z |
| _version_ |
1837799009363689472 |
| fulltext |
“adm-n2” — 2019/7/14 — 21:27 — page 269 — #119
Algebra and Discrete Mathematics RESEARCH ARTICLE
Volume 27 (2019). Number 2, pp. 269–279
c© Journal “Algebra and Discrete Mathematics”
On the inclusion ideal graph of a poset
N. Jahanbakhsh, R. Nikandish∗, M. J. Nikmehr
Communicated by V. Dlab
Abstract. Let (P,6) be an atomic partially ordered set
(poset, briefly) with a minimum element 0 and I(P ) the set of
nontrivial ideals of P . The inclusion ideal graph of P , denoted by
Ω(P ), is an undirected and simple graph with the vertex set I(P )
and two distinct vertices I, J ∈ I(P ) are adjacent in Ω(P ) if and only
if I ⊂ J or J ⊂ I. We study some connections between the graph
theoretic properties of this graph and some algebraic properties
of a poset. We prove that Ω(P ) is not connected if and only if
P = {0, a1, a2}, where a1, a2 are two atoms. Moreover, it is shown
that if Ω(P ) is connected, then diam(Ω(P )) 6 3. Also, we show that
if Ω(P ) contains a cycle, then girth(Ω(P )) ∈ {3, 6}. Furthermore, all
posets based on their diameters and girths of inclusion ideal graphs
are characterized. Among other results, all posets whose inclusion
ideal graphs are path, cycle and star are characterized.
1. Introduction
Recently, a major part of research in algebraic combinatorics has been
devoted to the application of graph theory and combinatorics in abstract
algebra. There are a lot of papers which apply combinatorial methods to
obtain algebraic results in poset theory (for example see [3, 5, 6] and [7]).
Let (P,6) be a poset with a least element 0. An element m ∈ P is
called maximal, if for every element p ∈ P the relation m 6 p implies
∗The corresponding author.
2010 MSC: 06A07; 05C25.
Key words and phrases: poset, inclusion ideal graph, diameter, girth, connec-
tivity.
“adm-n2” — 2019/7/14 — 21:27 — page 270 — #120
270 On the inclusion ideal graph of a poset
that m = p. We denote the set of maximal elements of P by Max(P ).
A minimal element of P is defined in a dual manner. We say x, y are
comparable in P if either x < y or y < x. A nonempty subset S of P is
a chain in P , if every two elements of S are comparable. A finite chain
with n elements can be written in the form c1 < c2 < · · · < cn. Such a
chain said to have length n− 1. If a < b, then a chain from a to b in P is
a chain in P whose minimum element is a and whose maximum element
is b. An order ideal or a lower set (an order filter or an upper set) of
P is a non-empty subset I ⊆ P (F ⊆ P ) such that for every x, y ∈ P ,
the relations x ∈ I and y 6 x imply that y ∈ I (for every x, y ∈ P , the
relations x ∈ F and x 6 y imply that y ∈ F ). The set of all ideals of P is
denoted by J (P ) and I(P ) = J (P ) \ {{0}, P}. For every element x of P ,
the ideal (x] := {y ∈ P |y 6 x}( the filter [x) := {y ∈ P |x 6 y}) is called
principal whose generator is x. Let x, y ∈ P . We say that y covers x in P
if x < y and no element in P lies strictly between x and y. If y covers x,
then we write x ⊏ y. Any cover of 0 in P is called an atom. The set of all
atoms of P is denoted by Atom(P ). The poset P is called atomic, if for
every non-zero element x ∈ P , we have (x]∩Atom(P ) 6= ∅. The set of all
principal ideal generated by Atom(P ) and P \Atom(P ) are denoted by
A(P ) and B(P ), respectively. For any undefined notation or terminology
in graph theory, we refer the reader to [8, 9].
Let G = (V,E) be a graph, where V = V (G) is the set of vertices
and E = E(G) is the set of edges. The degree of a vertex v in a graph
G is the number of edges incident with v. The degree of a vertex v is
denoted by deg(v). Let r be a non-negative integer. The graph G is said
to be r-regular, if the degree of each vertex is r. The set of all adjacent
vertices to v ∈ V is denoted by N(v). If u and v are two adjacent vertices
of G, then we write u−−v. We say that G is a connected graph if there
is a path between each pair of distinct vertices of G. For two vertices x
and y, let d(x, y) denote their distance, that is, the length of the shortest
path between x and y (we set d(x, y) := ∞ if there is no such path). The
diameter of G is diam(G) = sup{d(x, y) | x and y are distinct vertices
of G}. The girth of G, denoted by girth(G), is the length of the shortest
cycle in G (girth(G) = ∞ if G has no cycles). A graph is called complete,
if every pair of distinct vertices is joined by an edge. A complete graph
of order n is denoted by Kn. A bipartite graph is one whose vertex-set
can be partitioned into two (not necessarily nonempty) disjoint subsets in
such a way that the two end vertices for each edge lie in distinct partitions.
Among bipartite graphs, a complete bipartite graph is one in which each
vertex is joined to every vertex that is not in the same partition. The
complete bipartite graph with part sizes m and n is denoted by Km,n.
“adm-n2” — 2019/7/14 — 21:27 — page 271 — #121
N. Jahanbakhsh, R. Nikandish, M. J. Nikmehr 271
Graphs of the form K1,n are called star graphs. A graph G is k-partite if
V (G) can be expressed as the union of k (possibly empty) independent
sets. A cycle graph is a graph that consists of a single cycle. For any
undefined notation or terminology in graph theory, we refer the reader to
[2, 10].
Throughout this paper P is a nontrivial atomic poset with a minimum
element 0 and Atom(P ) = {a1, a2, . . . , an, . . .} (at most countably infinite).
The inclusion ideal graph of P , denoted by Ω(P ), is an undirected and
simple graph with the vertex set I(P ) and two distinct vertices I, J ∈ I(P )
are adjacent in Ω(P ) if and only if I ⊂ J or J ⊂ I. The idea of inclusion
ideal graph associated with a ring was first introduced and studied in [1].
Motivated by [1], we define and study the inclusion ideal graph of a poset.
In this paper, all posets whose inclusion ideal graphs are not connected
are classified. Also, if Ω(P ) is connected and contains a cycle, then upper
bounds for the diameter and the girth of Ω(P ) are given. Moreover, all
posets based on their diameters and girths of inclusion ideal graphs are
characterized.
2. Connectivity, diameter and girth of Ω(P )
In this section, we study the connectivity, diameter and girth of an
inclusion ideal graph associated with a poset. For instance, we characterize
all posets whose inclusion ideal graphs are connected. Moreover, it is
shown that the diameter of a connected inclusion ideal graph is at most
three. Furthermore, we classify inclusion ideal graphs of posets in terms
of their diameters and girthes.
We begin with the following lemma.
Lemma 2.1. Let (P,6) be a poset. Then the following statements hold.
(i) |V (Ω(P ))| = 0 if and only if |P | = 2.
(ii) |V (Ω(P ))| = 1 if and only if P is a chain with |P | = 3.
Proof. (i) It is clear.
(ii) First suppose that |V (ΩUM (P ))| = 1. If P is not a chain. Then P
has at least two non-comparable elements say x, y. Obviously, (x], (y] ∈
I(P ), which is impossible. Moreover, if x, y ∈ P and a1 ⊏ x and x ⊏ y,
then ΩUM (P ) has two vertices, a contradiction. Therefore |P | = 3.
The converse is clear.
Two following lemmas have straightforward proofs and so their proofs
are omitted.
“adm-n2” — 2019/7/14 — 21:27 — page 272 — #122
272 On the inclusion ideal graph of a poset
Lemma 2.2. Let (P,6) be a poset. Then the following statements hold.
(i) If P is a chain, then |J (P )| = |P |.
(ii) For every I ∈ I(P ), there exists J ∈ A(P ) such that J ⊂ I.
(iii) Let x, y ∈ P . If x < y, then (x] ⊂ (y].
Lemma 2.3. Let (P,6) be a poset and I, J be two ideals of P . Then
I ∩ J and I ∪ J are ideals of P .
By using Lemma 2.3, we characterize all posets whose inclusion ideal
graphs are not connected.
Theorem 2.4. Let (P,6) be a poset. Then Ω(P ) is not connected if and
only if P = {0, a1, a2}.
Proof. First, suppose that Ω(P ) is not connected and C1, . . . , Ck are
components of Ω(P ). Since Ω(P ) is not connected, we deduce that k > 2.
Let Ii ∈ Ci and Ij ∈ Cj , for some 1 6 i, j 6 k. Obviously, Ii and Ij are
not comparable. If Ii ∩ Ij 6= 0, then by Lemma 2.3, one may find the path
Ii−Ii∩Ij−Ij , which is impossible. Thus Ii∩Ij = 0. Therefore, there exist
atoms ai ∈ Ii \ Ij and aj ∈ Ij \ Ii. Consider the minimal ideals I = {0, ai}
and J = {0, aj}. It is clear that I ∈ Ci and J ∈ Cj . If I ∪ J 6= P , then
by Lemma 2.3, one may find the path I − I ∪ J − J in Ω(P ) and this
contradicts the hypothesis. Hence I ∪ J = P = {0, ai, aj}. This means
that k = 2, as desired.
Conversely, suppose that P = {0, a1, a2}. Let I1 = {0, a1} and I2 =
{0, a2}. Then I(P ) = {I1, I2}. Therefore, two isolated vertices I1, I2 form
Ω(P ) and so the proof is complete.
The next theorem states that the diameter of a connected inclusion
ideal graph associated with a poset does not exceed three.
Theorem 2.5. If Ω(P ) is connected, then diam(Ω(P )) 6 3.
Proof. Let Ii and Ij be two non-adjacent vertices of Ω(P ). If Ii ∩ Ij 6= 0,
then by Lemma 2.3, we have the path Ii − Ii ∩ Ij − Ij . Hence suppose
that Ii ∩ Ij = 0. Therefore, there exist atoms ai ∈ Ii \ Ij and aj ∈ Ij \ Ii.
Since Ω(P ) is connected, we deduce from Theorem 2.4 that {0, ai, aj} is
a vertex of Ω(P ). Now, we continue the proof in the following cases:
Case 1. If Ii = {0, ai} and Ij 6= {0, aj}, then consider the path
Ii − {0, ai, aj} − {0, aj} − Ij . The case Ii 6= {0, ai} and Ij = {0, aj} is
similar.
Case 2. If Ii = {0, ai} and Ij = {0, aj}, then we have the path
Ii − {0, ai, aj} − Ij .
“adm-n2” — 2019/7/14 — 21:27 — page 273 — #123
N. Jahanbakhsh, R. Nikandish, M. J. Nikmehr 273
Case 3. Let Ii 6= {0, ai} and Ij 6= {0, aj}. If {0, ai} ∪ Ij 6= P , then we
have the path Ii − {0, ai} − {0, ai} ∪ Ij − Ij . Hence, we may suppose that
{0, ai} ∪ Ij = P . We claim that {0, aj} ∪ Ii 6= P . Assume to the contrary,
{0, aj} ∪ Ii = P . Thus
0 = Ii ∩ Ij = (P \ {aj}) ∩ (P \ {ai}).
Thus P = {0, ai, aj}. By Theorem 2.4, Ω(P ) is not connected, a contra-
diction and so the claim is proved. Therefore, Ii links to Ij through the
path Ii − {0, aj} ∪ Ii − {0, aj} − Ij .
The proof now is complete.
To characterize inclusion ideal graphs in terms of their diameters, the
following lemma is needed.
Lemma 2.6. Let (P,6) be a poset and I, J ∈ I(P ). Then the following
statements hold:
(i) d(I, J) = 1 if and only if I and J are comparable.
(ii) d(I, J) = 2 if and only if I and J are not comparable and either
I ∩ J 6= 0 or I ∪ J 6= P .
(iii) d(I, J) > 3 if and only if I ∩ J = 0 and I ∪ J = P .
Proof. (i) It is clear.
(ii) Let d(I, J) = 2. Then there exists K ∈ I(P ) such that d(I,K) =
d(K, J) = 1. It is obvious that I and J are not comparable. We show that
either I ∩ J 6= 0 or I ∪ J 6= P . If K ⊂ I and K ⊂ J , then I ∩ J 6= 0. If
I ⊂ K and J ⊂ K, then I ∪ J ⊆ K and so I ∪ J 6= P . Note that the case
I ⊂ K ⊂ J does not occur. The converse is clear.
(iii) It follows from parts (i) and (ii).
Theorem 2.7. Let (P,6) be a poset such that Ω(P ) be connected. Then
the following statements hold:
(i) diam(Ω(P )) = 1 if and only if P is a chain.
(ii) diam(Ω(P )) = 2 if and only if |P | > 4 and one of the following
conditions holds:
(a) |Atom(P )| = 1 and P is not a chain.
(b) |Atom(P )| > 2 and [ai)∩ [aj) 6= ∅, for every ai, aj ∈ Atom(P ).
(iii) diam(Ω(P )) = 3 if and only if |Atom(P )| > 2, |P | > 4 and there
exists at least one ai in Atom(P ) such that for every aj ∈ Atom(P )
with j 6= i, [ai) ∩ [aj) = ∅.
Proof. (i) Suppose that Ω(P ) is complete. We claim that P has a unique
atom. If a1, a2 are two distinct atoms of P , then vertices I1 = {0, a1}
“adm-n2” — 2019/7/14 — 21:27 — page 274 — #124
274 On the inclusion ideal graph of a poset
and I2 = {0, a2} are not adjacent (as obviously they are not comparable),
a contradiction and so the claim is proved. Similarly, P has a unique
maximal element, say m1. Let x, y be two non-comparable elements of P .
Thus x 6= a1,m1 and y 6= a1,m1 and hence vertices (x] and (y] are not
adjacent in Ω(P ), which is impossible. Hence every pair of elements of P
are comparable, as desired.
Conversely, assume that P is a chain, say 0 < a1 < x1 < x2 < · · · <
xn−1 < xn, where n + 1 is the length of chain. Then I1 = {0, a1}, Ii =
{0, a1, xi−1}(2 6 i 6 n) are all ideals of P . It is clear that I1 ⊂ I2 ⊂ · · · ⊂
In, i.e, Ω(P ) is complete.
(ii) First, suppose that diam(Ω(P )) = 2. Then, there exist distinct
vertices I, J ∈ I(P ) such that d(I, J) = 2. Therefore, there is K ∈ I(P )
such that d(I,K) = d(K, J) = 1. By Lemma 2.1 and Theorem 2.4,
|P | > 4. Also, by part (i), P is not a chain. Obviously, |Atom(P )| > 1.
If |Atom(P )| 6= 1, then we show that [ai) ∩ [aj) 6= ∅, for every ai, aj ∈
Atom(P ). Assume to the contrary, there exists ai ∈ Atom(P ) such that
[ai) ∩ [aj) = ∅, for every aj( 6= ai) ∈ Atom(P ). Thus [ai) ∪ {0} ∈ I(P ).
Now, consider the path [ai)∪ {0}− {0, ai}− {0, ai} ∪ (P \ [ai))−P \ [ai).
By part (iii) of Lemma 2.6, d([ai) ∪ {0}, P \ [ai)) = 3. This contradicts
the assumption diam(Ω(P )) = 2.
Conversely, assume that |P | > 4. If (a) holds, then |Atom(P )| = 1
implies that diam(Ω(P )) 6 2. Also, since P is not a chain, we de-
duce that diam(Ω(P )) = 2. Next, let (b) holds. Assume to the con-
trary, diam(Ω(P )) 6= 2. Then, by Theorem 2.5, diam(Ω(P )) = 1 or 3.
If diam(Ω(P )) = 1, then by part (i), P is a chain, a contradiction. If
diam(Ω(P )) = 3, then by part (iii) of Lemma 2.6, there exist I, J ∈
V (Ω(P )) such that I ∪ J = P and I ∩ J = {0}. Therefore, there are
atoms ai ∈ I \ J and aj ∈ J \ I. Let y ∈ [ai) ∩ [aj). With no loss of
generality, we may assume that y ∈ I \ J . Thus aj ∈ I, which is impos-
sible and so [ai) ∩ [aj) = ∅. This contradicts the assumption and hence
diam(Ω(P )) = 2.
(iii) It is obvious by parts (i) and (ii).
In the next result we study the girth of an inclusion ideal graph of a
poset.
Theorem 2.8. Let (P,6) be a poset. Then the following statements hold.
(i) girth(Ω(P )) = 3 if and only if |P | > 5.
(ii) girth(Ω(P )) = 6 if and only if |P | = 4 and |Atom(P )| = 3.
(iii) girth(Ω(P )) = ∞ if and only if |P | < 5 and |Atom(P )| 6= 3.
“adm-n2” — 2019/7/14 — 21:27 — page 275 — #125
N. Jahanbakhsh, R. Nikandish, M. J. Nikmehr 275
Proof. (i) Let |P | > 5. If |Atom(P )| > 3 and a1, a2, a3 ∈ Atom(P ),
then Ω(P ) has the cycle {0, a1}− {0, a1, a2}− {0, a1, a2, a3}− {0, a1}. To
complete the proof, suppose that |Atom(P )| < 3. First, let |Atom(P )| = 1.
Two following cases may occur:
Case 1. If P is a chain, then by part (i) of Theorem 2.7, Ω(P ) is
complete. Since |P | > 5, we deduce that girth(Ω(P )) = 3.
Case 2. If P is not a chain, then there exist at least two non-comparable
elements in P , say x, y. Obviously, a1 6= x and a1 6= y. If (x] ∪ (y] 6= P ,
then by Lemma 2.3, the triangle {0, a1}− (x]− (x]∪ (y]−{0, a1} in Ω(P )
shows that girth(Ω(P )) = 3. Hence suppose that (x]∪(y] = P . This means
that x, y are only maximal elements of P . Since |P | > 5, with no loss of
generality, one may assume that there exists a non atom z ∈ P such that
z < x. Now, by part (c) of Lemma 2.2, the cycle {0, a1}−(z]−(x]−{0, a1}
implies that girth(Ω(P )) = 3.
Finally, let Atom(P ) = {a1, a2}. Since |P | > 5, there exists an element
x ∈ P such that either a1 ⊏ x or a2 ⊏ x. The cycle {0, a1}− {0, a1, a2}−
{0, a1, a2, x} − {0, a1} shows that girth(Ω(P )) = 3.
Conversely, suppose that girth(Ω(P )) = 3. Thus there exists a cycle of
length three in Ω(P ), say I1 − I2 − I3 − I1. With no loss of generality, we
suppose that I1 ⊂ I2 ⊂ I3. Since every ideals needs at least two elements
and every Ii (1 6 i 6 3) is non-trivial, we deduce that |P | > 5.
(ii) Let P ={0, a1, a2, a3}. Then Ω(P ) is the cycle {0, a1}−{0, a1, a2}−
{0, a2}−{0, a2, a3}−{0, a3}−{0, a1, a3}−{0, a1} and so girth(Ω(P )) = 6.
Conversely, suppose that girth(Ω(P )) = 6. By part (i), |P | < 5. It follows
from part (i) of Lemma 2.1 that 3 6 |P | 6 4. If |P | = 3 and |Atom(P )| = 1,
then part (ii) of Lemma 2.1 implies that Ω(P ) = K1, a contradiction.
Also, if P = {0, a1, a2}, then by Theorem 2.4, Ω(P ) is not connected, a
contradiction. Hence we may suppose that |P | = 4. By part (i) of Theorem
2.7, P is not a chain and so |Atom(P )| > 2. If P = {0, a1, a2, x}, where
x is not an atom, then two following cases may occur:
Case 1. a1 ⊏ x and a2 ⊏ x. It is not hard to check that |I(P )| = 3,
i.e, girth(Ω(P )) 6= 6, a contradiction.
Case 2. a1 ⊏ x and a2, x are not comparable. In this case, |I(P )| = 4
and so girth(Ω(P )) 6= 6, a contradiction. The case “a2 ⊏ x and a1, x are
not comparable” is similar.
Two above cases show that |Atom(P )| = 3.
(iii) If girth(Ω(P )) = ∞, then by parts (i) and (ii), we deduce that
|P | < 5 and |Atom(P )| 6= 3. Conversely, suppose that |P | < 5 and
|Atom(P )| 6= 3. The following cases may happen:
Case 1. |P | = 4 and |Atom(P )| = 2. By proof of part (ii), either
|I(P )| = 3 or |I(P )| = 4. It is not hard to see that if |I(P )| = 3, then
“adm-n2” — 2019/7/14 — 21:27 — page 276 — #126
276 On the inclusion ideal graph of a poset
Ω(P ) is a path of length two (K1,2) and if |I(P )| = 4, then Ω(P ) is a
path of length three.
Case 2. |P | = 4 and |Atom(P )| = 1. If P is a chain, then by part (i)
of Theorem 2.7, Ω(P ) is K2. If P is not a chain, then Ω(P ) is K1,2.
Case 3. |P | = 3 and |Atom(P )| = 2. By Theorem 2.4, Ω(P ) is not
connected.
Case 4. |P | = 3 and |Atom(P )| = 1. By part (ii) of Lemma 2.1, Ω(P )
is K1.
Case 5. |P | = 2. By part (i) of Lemma 2.1, Ω(P ) is the empty graph.
In all of the above cases, girth(Ω(P )) = ∞, as desired.
We close this section with the following corollary which is an immediate
consequence of Theorem 2.8.
Corollary 2.9. Let (P,6) be a poset. Then girth(Ω(P )) ∈ {3, 6,∞}.
3. Some further classifications of Ω(P )
In this section, some further classifications of Ω(P ) are given. For
instance, we classify all poset whose inclusion ideal graphs are regular.
Moreover, it is shown that if (P,6) is a finite poset with connected Ω(P ),
then Ω(P ) is a (|P | − 2)-partite graph. Finally, posets whose inclusion
ideal graphs are cycles or paths are characterized.
Theorem 3.1. Let (P,6) be a finite poset. Then Ω(P ) is regular if and
only if P is one of the following posets.
a. P is a chain.
b. P = Atom(P ) ∪ {0} with |P | 6 4.
Proof. Suppose that Ω(P ) is a regular graph. If there exists a vertex of
V (Ω(P )) which is adjacent to every other vertex, then Ω(P ) is complete.
Thus by part (i) of Theorem 2.7, P is a chain. So assume that there is no
vertex of V (Ω(P )) adjacent to every other vertex. Hence |Atom(P )| > 2.
Consider the following cases:
Case 1. P = Atom(P ) ∪ {0}. If |Atom(P )| = 2, then by Theorem 2.4,
Ω(P ) is 0-regular. If |Atom(P )| = 3, then by part (ii) of Theorem 2.8,Ω(P )
is 2-regular. Let Atom(P ) = {a1, . . . , an}, where n > 3. If I = {0, a1} and
J = {0, a1, a2}, then it is not hard to check that
deg(I) = (n− 1) +
(
n− 1
2
)
+
(
n− 1
3
)
+ · · ·+
(
n− 1
n− 2
)
,
“adm-n2” — 2019/7/14 — 21:27 — page 277 — #127
N. Jahanbakhsh, R. Nikandish, M. J. Nikmehr 277
whereas
deg(J) = 2 +
(
n− 2
1
)
+
(
n− 2
2
)
+ · · ·+
(
n− 2
n− 3
)
.
Since n > 3, we deduce that deg(I) > deg(J), a contradiction.
Case 2. P 6= Atom(P ) ∪ {0}. Thus there exists an element x ∈ P \
Atom(P ). With no loss of generality, one may assume that a1 < x and
there is no y ∈ P such that a1 < y < x. Let I ′ = {0, a1} and J ′ = {0, a1, x}.
Since Ω(P ) is regular, we conclude that P 6= {0, a1, a2, x} and so |P | > 5.
It is not hard to check that N(J ′) = {I ′, {L}L∈B}, where B consists of all
ideals of P which contains J ′ and N(I ′) ⊆ N(J ′)∪{{0, a1, a2}}. It means
that deg(I ′) > deg(J ′), which is impossible. This completes the proof.
Next, we show that if (P,6) is a finite poset with connected Ω(P ),
then Ω(P ) is a (|P |−2)-partite graph. First, we state the following lemma.
Lemma 3.2. Let (P,6) be a finite poset. Then the cardinal number of
every minimal ideal is 2 and the cardinal number of every maximal ideal
is |P | − 1.
Proof. It is not hard to check that every minimal ideal is of the form
{0, ai}, where ai ∈ Atom(P ), and every maximal ideal is of the form
P \ {u}, where u is a maximal element of P . Thus the result follows.
Theorem 3.3. Let (P,6) be a finite poset. If Ω(P ) is connected, then
Ω(P ) is a (|P | − 2)-partite graph.
Proof. Let I be an ideal of P . By Lemma 3.2, 2 6 |I| 6 |P | − 1. We
claim that for every i, 2 6 i 6 |P | − 1, there exists at least one ideal
I of P such that |I| = i. Assume that Max(P ) = {m1, . . . ,mk} and
M1 = P − {m1} is a maximal ideal of P . Set Mi = Mi−1 − {mi}, for
every 2 6 i 6 k. Obviously, Mi is an ideal of order |P | − i, for every i,
1 6 i 6 k. Let {n1, . . . , ns} be maximal elements of Mk (with respect to
elements contained in Mk). By repeating the above procedure, we obtain
an ideal of order |P | − k − j, for every j, 1 6 j 6 s. By this method,
our claim is proved. Define the relation ∼ on V (Ω(P )) as follows: For
ever I, J ∈ V (Ω(P )) we write I ∼ J if and only if |I| = |J |. It is easily
seen that ∼ is an equivalence relation on V (Ω(P )). By [I], we mean the
equivalence class of I. It follows from the above argument that the number
of equivalence classes is equal to |P | − 2. Now, suppose that [I] and [J ]
are two distinct arbitrary equivalence classes. It is easily seen that there is
no adjacency between every pair of vertices contained [I] and every vertex
“adm-n2” — 2019/7/14 — 21:27 — page 278 — #128
278 On the inclusion ideal graph of a poset
contained in [I] is adjacent to at least one vertex contained in [J ]. This
completes the proof.
Next we classify posets whose inclusion ideal graphs are cycles or
paths.
Theorem 3.4. Let (P,6) be a poset. Then Ω(P ) is a cycle if and only if
one of the following statements holds.
(i) P is a chain and |P | = 5.
(ii) |P | = 4 and |Atom(P )| = 3.
Proof. Suppose that Ω(P ) is a cycle of length n. By Theorem 2.8, either
n = 3 or n = 6. If n = 3, then Ω(P ) is a complete graph. Thus part (i)
of Theorem 2.7 implies that P is a chain. Also, by part (i) of Theorem
2.8, |P | > 5. It is not hard to check that |P | > 5 implies that |I(P )| > 3,
which is impossible. Hence |P | = 5. If n = 6, then the result follows from
part (ii) of Theorem 2.8. Conversely,
(i) Suppose that P is a chain with P = {0, a1, x1, x2, x3}. Then Ω(P )
is the cycle {0, a1} − {0, a1, x1} − {0, a1, x1, x2} − {0, a1} of length 3.
(ii) If P = Atom(P )∪{0} with |P | = 5, then by part (ii) of Theorem 2.8,
Ω(P ) is a cycle of length 6.
The proof is complete.
Theorem 3.5. Let (P,6) be a poset. Then Ω(P ) is a path of positive
length if and only if |P | = 4 and |Atom(P )| 6= 3.
Proof. The result follows from Theorem 2.8.
In the following result, we classify posets whose inclusion ideal graphs
are star.
Theorem 3.6. Let (P,6) be a poset. Then Ω(P ) is a star graph if and
only if |P | = 4 and one of the following statements holds.
(i) P is a chain (Ω(P ) = K2).
(ii) P is not a chain and |I(P )| = 3 (Ω(P ) = K1,2).
Proof. Suppose that Ω(P ) is star. By Theorem 2.8, |P | < 5. If |P | < 4,
then Ω(P ) is not star. Thus |P | = 4. Two following cases may occur.
(i) If P is a chain, then by part (i) of Theorem 2.7, Ω(P ) = K2.
(ii) Suppose that P is not a chain. If P = {0, a1, x, y}, then Ω(P ) is
the star graph {0, a1, x} − {0, a1} − {0, a1, y}. Thus we may assume that
P = {0, a1, a2, x}. If a1 < x and a2 < x, then Ω(P ) is the the star graph
{0, a1} − {0, a1, a2} − {0, a2}. If a1 < x and a2 ≮ x, then Ω(P ) is the
the path {0, a1, x} − {0, a1} − {0, a1, a2} − {0, a2}, which is impossible.
“adm-n2” — 2019/7/14 — 21:27 — page 279 — #129
N. Jahanbakhsh, R. Nikandish, M. J. Nikmehr 279
The case a2 < x and a1 ≮ x leads to a similar contradiction. Also, if
P = {0, a1, a2, a3}, then by part (iii) of Theorem 2.8, Ω(P ) is a cycle of
length 6. Thus |I(P )| = 3 and Ω(P ) = K1,2.
The converse is clear.
In light of Theorems 2.8 and 3.6, we have the following corollary.
Corollary 3.7. Let (P,6) be a poset. Then the following statements are
equivalent:
(i) Ω(P ) is complete bipartite.
(ii) Ω(P ) is star.
(iii) Either Ω(P ) = K2 or Ω(P ) = K1,2.
Acknowledgements. The authors thank to the referee for his/her careful
reading and his/her excellent suggestions.
References
[1] S. Akbari, M. Habibi, A. Majidinia, R. Manaviyat, The inclusion ideal graph of
rings, Comm. Algebra, 43 (2015) 2457–2465.
[2] J. A. Bondy, U. S. R. Murty, Graph Theory with Applications, American Elsevier,
New York, 1976.
[3] Y. Civan, Upper maximal graphs of posets, Order, 30 (2013) 677—688.
[4] R. Halaš, M. Jukl, On Beck’s coloring of posets, Discrete Math, 309 (2009) 4584–
4589.
[5] V. Joshi, Zero divisor graph of a poset with respect to an ideal, Order, 29 (2012)
499-–506.
[6] J. D. LaGrange, K. A. Roy, Poset graphs and the lattice of graph annihilators,
Discrete Math, 313 (2013) 1053—1062.
[7] S. K. Nimbhorkar, M. P. Wasadikar, L. DeMeyer, Coloring of semilattices, Ars
Combin, 12 (2007) 97–104.
[8] S. Roman, Lattices and Ordered Sets, Springer, New York, 2008.
[9] S. Rudeanu, Sets and Ordered Structures, University of Bucharest, Romania, 2012.
[10] D. B. West, Introduction to Graph Theory, 2nd ed., Prentice Hall, Upper Saddle
River, 2001.
Contact information
N. Jahanbakhsh,
M. J. Nikmehr
Department of Mathematics, Karaj Branch,
Islamic Azad University, Karaj, Iran
E-Mail(s): n.jahanbakhsh@yahoo.com,
nikmehr@kntu.ac.ir
R. Nikandish Department of Basic Sciences, Jundi-Shapur
University of Technology, Dezful, Iran
E-Mail(s): r.nikandish@jsu.ac.ir
Received by the editors: 23.07.2016
and in final form 23.07.2017.
|