### 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 ≤*y. The

_{P}*strict-double-bound number*ζ(

*G*) of a graph

*G*is defined as min{ n ; sDB(

*P*) ≅

*G*∪

*Ǩ*{for some poset

_{n}*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

#### Full Text:

PDFDOI: http://dx.doi.org/10.5614/ejgta.2021.9.2.16

#### References

G.A. Cheston and T.S. Jap, A survey of the algorithmic properties of simplicial, upper bound and middle graphs, J. Graph Algorithms Appl. 10 (2006), 159–190.

M.C. Golumbic, Algorithmic Graph Theory and Perfect Graphs, Academic Press, New York, 1980.

S. Konishi, K. Ogawa, S. Tagusari, and M. Tsuchiya, Note on strict-double-bound numbers of paths, cycles, and wheels, J. Combin. Math. Combin. Comput. 83 (2012), 205–210.

L. Langley, S.K. Merz, J.R. Lundgren, and C.W. Rasmussen, Posets with interval or chordal strict upper and lower bound graphs, Congr. Numer. 125 (1997), 153–160.

I.-J. Lin, T.A. McKee, and D.B. West, The leafage of a chordal graph, Discuss. Math. Graph Theory 18 (1998), 23–48.

F.R. McMorris and T. Zaslavsky, Bound graphs of a partially ordered set, J. Comb. Inf. Syst. Sci. 7 (1982), 134–138.

K. Ogawa, K. Shiraki, S. Tagusari, and M. Tsuchiya, On strict-double-bound numbers of complete pseudo-regular trees, Far East Journal of Applied Mathematics 93 (2015), 1–19.

K. Ogawa, S. Tagusari, and M. Tsuchiya, Note on strict-double-bound graphs and numbers, AKCE Int. J. Graphs Comb. 11 (2014),127–132.

D.J. Rose, Triangulated graphs and the elimination process, Journal of Mathematical Analysis and Applications 32 (1970), 597–609.

D.D. Scott, Posets with interval upper bound graphs, Order 3 (1986), 269–281.

D.D. Scott, The competition-common enemy graph of a digraph, Discrete Appl. Math. 17 (1987), 269–280.

### Refbacks

- There are currently no refbacks.

ISSN: 2338-2287

This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.