On the essential graph of a poset

Articles in Press

Document Type : Original paper

Authors

1 Department of Mathematics, Jundi-Shapur University of Technology, Dezful, Iran

2 Department of Physics, Technical and Vocational University (TVU), Tehran, Iran

Abstract

Let (P,≤) be an atomic partially ordered set (briefly, a poset) with a minimum element 0, and let I(P) be the set of all nontrivial ideals of P. The essential graph of P, denoted by Ge(P), is an undirected, simple graph with the vertex set I(P) and two distinct vertices I,J∈I(P) are adjacent in Ge(P) if and only if I∪J is an essential ideal of P. We study the connections between the graph-theoretic properties of this graph and the algebraic properties of a poset. We prove that Ge(P) is connected with diameter at most three. Furthermore, all posets are characterized based on the diameters of their essential graphs. Also, all posets with planar Ge(P) are classified. Among other results, the clique number and chromatic number of Ge(P) are determined.

Keywords

Main Subjects

References

[1] J.A. Bondy and U.S.R. Murty, Graph Theory, Springer Publishing Company, Incorporated, New York, 2008.
[2] Y. Civan, Upper maximal graphs of posets, Order 30 (2013), 677–688. https://doi.org/10.1007/s11083-012-9270-4
[3] R. Halaš and M. Jukl, On Beck’s coloring of posets, Discrete Math. 309 (2009), no. 13, 4584–4589. https://doi.org/10.1016/j.disc.2009.02.024
[4] V. Joshi, Zero divisor graph of a poset with respect to an ideal, Order 29 (2012), 499–506. https://doi.org/10.1007/s11083-011-9216-2
[5] J.D. LaGrange and K.A. Roy, Poset graphs and the lattice of graph annihilators, Discrete Math. 313 (2013), no. 10, 1053–1062.  https://doi.org/10.1016/j.disc.2013.02.004
[6] M.J. Nikmehr, R. Nikandish, and M. Bakhtyiari, On the essential graph of a commutative ring, J. Algebra Appl. 16 (2017), no. 7, Article ID: 1750132. https://doi.org/10.1142/S0219498817501328
[7] S.K. Nimbhorkar, M.P. Wasadikar, and L. DeMeyer, Coloring of semilattices, Ars Combin. 12 (2007), 97–104.
[8] S. Roman, Lattices and Ordered Sets, Springer Science & Business Media, New York, 2008.
[9] S. Rudeanu, Sets and Ordered Structures, Bentham Science Publishers, 2012.
[10] D.B. West, Introduction to Graph Theory, Prentice hall Upper Saddle River, 2001.
Communications in Combinatorics and Optimization

Articles in Press, Accepted Manuscript
Available Online from 29 June 2025

Files

Share

How to cite

Statistics