On strict-double-bound numbers of graphs and cut sets
| Main Authors: | Ikeda, Kazutaka; Department of Mathematical Sciences, Tokai University, Hiratsuka 259-1292, Japan, Ogawa, Kenjiro; Department of Mathematical Sciences, Tokai University, Hiratsuka 259-1292, Japan, Tagusari, Satoshi; Department of Mathematical Sciences, Tokai University, Hiratsuka 259-1292, Japan, Tashiro, Shin-ichiro; Department of Mathematical Sciences, Tokai University, Hiratsuka 259-1292, Japan, Tsuchiya, Morimasa; Department of Mathematical Sciences, Tokai University, Hiratsuka 259-1292, Japan |
|---|---|
| Other Authors: | Morimasa Tsuchiya, Tokai University, Department of Mathematical Sciences |
| Format: | Article info application/pdf eJournal |
| Bahasa: | eng |
| Terbitan: |
GTA Research Group, Univ. Newcastle, Indonesian Combinatorics Society and ITB
, 2021
|
| Subjects: | |
| Online Access: |
https://www.ejgta.org/index.php/ejgta/article/view/793 https://www.ejgta.org/index.php/ejgta/article/view/793/pdf_191 |
Daftar Isi:
- 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.