Outer-connected domination in graphs

被引：0
|
作者：
Jiang, Hongxing [2 ]
Shan, Erfang [1 ]
机构：
[1] Shanghai Univ, Dept Math, Shanghai 200444, Peoples R China
[2] Wenzhou Univ, Coll Math & Informat Sci, Wenzhou 325000, Peoples R China
来源：
UTILITAS MATHEMATICA | 2010年 / 81卷
关键词：
Outer-connected domination; Nordhaus-Gaddum-type inequality; Tree;
D O I：
暂无
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
A set S of vertices in a graph G = (V, E) is an outerconnected dominating set (OCDS) of G if S is a dominating set of G and G[V - S] is connected. The outer-connected domination number of G is the minimum cardinality of an OCDS of G. In this paper we characterize the graphs with large outer-connected domination number. Also, we give Nordhaus-Gaddum-type inequality on outer-connected domination and characterize the graphs with the right equality.
引用
收藏
页码：265 / 274
页数：10
相关论文
共 50 条
  • [21] On k-connected restrained domination in graphs
    Chen, Hongyu
    Chen, Xuegang
    Tan, Xiang
    ARS COMBINATORIA, 2011, 98 : 387 - 397
  • [22] Outer-weakly convex domination number of graphs
    Dayap, Jonecis A.
    Alcantara, Richard T.
    Anoos, Roma M.
    COMMUNICATIONS IN COMBINATORICS AND OPTIMIZATION, 2020, 5 (02) : 207 - 215
  • [23] On the Outer-Independent Double Roman Domination of Graphs
    Rao, Yongsheng
    Kosari, Saeed
    Sheikholeslami, Seyed Mahmoud
    Chellali, M.
    Kheibari, Mahla
    FRONTIERS IN APPLIED MATHEMATICS AND STATISTICS, 2021, 6
  • [24] Connected domination critical graphs with respect to relative complements
    Xue-gang Chen
    Liang Sun
    Czechoslovak Mathematical Journal, 2006, 56 : 417 - 423
  • [25] A note on connected bipartite graphs having independent domination number half their order
    Ma, DX
    Chen, XG
    APPLIED MATHEMATICS LETTERS, 2004, 17 (08) : 959 - 962
  • [26] Graphs that are simultaneously efficient open domination and efficient closed domination graphs
    Klavzar, Sandi
    Peterin, Iztok
    Yero, Ismael G.
    DISCRETE APPLIED MATHEMATICS, 2017, 217 : 613 - 621
  • [27] Bottleneck domination and bottleneck independent domination on graphs
    Yen, WCK
    JOURNAL OF INFORMATION SCIENCE AND ENGINEERING, 2002, 18 (02) : 311 - 331
  • [28] ON ACCURATE DOMINATION IN GRAPHS
    Cyman, Joanna
    Henning, Michael A.
    Topp, Jerzy
    DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2019, 39 (03) : 615 - 627
  • [29] TOTAL CONNECTED DOMINATION GAME
    Bujtas, Csilla
    Henning, Michael A.
    Irsic, Vesna
    Klavzar, Sandi
    OPUSCULA MATHEMATICA, 2021, 41 (04) : 453 - 464
  • [30] On Signed Star Domination in Graphs
    Yan-cai Zhao
    Er-fang Shan
    Lian-ying Miao
    Zuo-song Liang
    Acta Mathematicae Applicatae Sinica, English Series, 2019, 35 : 452 - 457
12345