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

Kazutaka Ikeda (Department of Mathematical Sciences, Tokai University, Hiratsuka 259-1292, Japan)
Kenjiro Ogawa (Department of Mathematical Sciences, Tokai University, Hiratsuka 259-1292, Japan)
Satoshi Tagusari (Department of Mathematical Sciences, Tokai University, Hiratsuka 259-1292, Japan)
Shin-ichiro Tashiro (Department of Mathematical Sciences, Tokai University, Hiratsuka 259-1292, Japan)
Morimasa Tsuchiya (Department of Mathematical Sciences, Tokai University, Hiratsuka 259-1292, Japan)

Electronic Journal of Graph Theory and Applications (EJGTA)
Vol 9, No 2 (2021): Electronic Journal of Graph Theory and Applications

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.