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

被引:0
|
作者
Ikeda, Kazutaka [1 ]
Ogawa, Kenjiro [1 ]
Tagusari, Satoshi [1 ]
Tashiro, Shin-ichiro [1 ]
Tsuchiya, Morimasa [1 ]
机构
[1] Tokai Univ, Dept Math Sci, Hiratsuka, Kanagawa 2591292, Japan
关键词
strict-double-bound graph; strict-double-bound number; cut-set; chordal graph;
D O I
10.5614/ejgta.2021.9.2.16
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
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 not equal v and there exist elements x, y is an element of X distinct from u and v such that x <=(P) u <=(P) y and x <=(P) v <=(P) y. The strict-doublebound number zeta(G) of a graph G is defined as min{ n; sDB(P) congruent to G U (K) over bar (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
引用
收藏
页码:443 / 449
页数:7
相关论文
共 8 条
  • [1] NOTE ON STRICT-DOUBLE-BOUND GRAPHS AND NUMBERS
    Ogawa, Kenjiro
    Tagusari, Satoshi
    Tsuchiya, Morimasa
    AKCE INTERNATIONAL JOURNAL OF GRAPHS AND COMBINATORICS, 2014, 11 (02) : 127 - 132
  • [2] On strict-double-bound numbers of caterpillars
    Ogawa, Kenjiro
    Shiraki, Yuhei
    Tagusari, Satoshi
    Tsuchiya, Morimasa
    DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS, 2015, 7 (03)
  • [3] ON STRICT-DOUBLE-BOUND NUMBERS OF COMPLETE GRAPHS WITHOUT EDGES OF STARS AND PANS
    Kanada, Keisuke
    Kushima, Kanosa
    Ogawa, Kenjiro
    Tagusari, Satoshi
    Tsuchiya, Morimasa
    ADVANCES AND APPLICATIONS IN DISCRETE MATHEMATICS, 2015, 16 (02): : 125 - 133
  • [4] Note on strict-double-bound numbers of nearly complete graphs missing some edges
    Ogawa, Kenjiro
    Soejima, Ryoko
    Tagusari, Satoshi
    Tsuchiya, Morimasa
    DISCRETE MATHEMATICS, 2012, 312 (03) : 584 - 587
  • [5] On strict-double-bound numbers of spiders and ladders
    Konishi, Syota
    Ogawa, Kenjiro
    Tagusari, Satoshi
    Tsuchiya, Morimasa
    ARS COMBINATORIA, 2013, 108 : 249 - 255
  • [6] On strict-double-bound graphs and Cartesian products of paths and cycles
    Egawa, Yoshimi
    Ogawa, Kenjiro
    Ozeki, Kenta
    Tagusari, Satoshi
    Tsuchiya, Morimasa
    DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS, 2024, 16 (05)
  • [7] An upper bound for the competition numbers of graphs
    Kamibeppu, Akira
    DISCRETE APPLIED MATHEMATICS, 2010, 158 (02) : 154 - 157
  • [8] CUT-SETS IN ZERO-DIVISOR GRAPHS OF FINITE COMMUTATIVE RINGS
    Cote, B.
    Ewing, C.
    Huhn, M.
    Plaut, C. M.
    Weber, D.
    COMMUNICATIONS IN ALGEBRA, 2011, 39 (08) : 2849 - 2861