Upper Maximal Graphs of Posets
ORDER-A JOURNAL ON THE THEORY OF ORDERED SETS AND ITS APPLICATIONS, cilt.30, sa.2, ss.677-688, 2013 (SCI-Expanded, Scopus)
- Yayın Türü: Makale / Tam Makale
- Cilt numarası: 30 Sayı: 2
- Basım Tarihi: 2013
- Doi Numarası: 10.1007/s11083-012-9270-4
- Dergi Adı: ORDER-A JOURNAL ON THE THEORY OF ORDERED SETS AND ITS APPLICATIONS
- Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus
- Sayfa Sayıları: ss.677-688
- Süleyman Demirel Üniversitesi Adresli: Evet
Özet
We introduce and study a class of simple graphs, the upper-maximal graphs (UM-graphs), associated to finite posets. The vertices of the UM-graph of a given poset P are the elements of P, and edges are formed by those vertices x and y whenever any maximal element of P that is greater than x is also greater than y or vise versa. We show that the class of UM-graphs constitutes a subclass of comparability graphs. We further provide a characterization of chordal UM-graphs, and compare UM-graphs with known bound graphs of posets.