On strict-double-bound numbers of graphs and cut sets

Abstract

For a poset P=(X,≤P), the strict-double-bound graph of P is the graph sDB(P) on V(sDB(P))=X for which vertices u and v of sDB(P) are adjacent if and only if u ≠ v and there exist elements x,y ∈ X distinct from u and v such that x ≤P u ≤P y and x ≤P v ≤P y. The strict-double-bound number ζ(G) of a graph G is defined as min{ n ; sDB(P) ≅ G ∪ Ǩn {for some poset P}. We obtain an upper bound of strict-double-bound numbers of graphs with a cut-set generating a complete subgraph. We also estimate upper bounds of strict-double-bound numbers of chordal graphs.

Keywords

• strict-double-bound graph
• strict-double-bound number
• cut-set
• chordal graph