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

Kazutaka Ikeda, Kenjiro Ogawa, Satoshi Tagusari, Shin-ichiro Tashiro, Morimasa Tsuchiya

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

Full Text:

PDF

DOI: 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

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

View EJGTA Stats