Upper Maximal Graphs of Posets


Civan Y.

ORDER-A JOURNAL ON THE THEORY OF ORDERED SETS AND ITS APPLICATIONS, cilt.30, ss.677-688, 2013 (SCI İndekslerine Giren Dergi) identifier identifier

  • Cilt numarası: 30 Konu: 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
  • Sayfa Sayısı: ss.677-688

Ö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.