Upper Maximal Graphs of Posets


Civan Y.

ORDER-A JOURNAL ON THE THEORY OF ORDERED SETS AND ITS APPLICATIONS, vol.30, no.2, pp.677-688, 2013 (Journal Indexed in SCI) identifier identifier

  • Publication Type: Article / Article
  • Volume: 30 Issue: 2
  • Publication Date: 2013
  • Doi Number: 10.1007/s11083-012-9270-4
  • Title of Journal : ORDER-A JOURNAL ON THE THEORY OF ORDERED SETS AND ITS APPLICATIONS
  • Page Numbers: pp.677-688

Abstract

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.