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 条
  • [1] The Outer-connected Domination Number of Sierpinski-like Graphs
    Chang, Shun-Chieh
    Liu, Jia-Jie
    Wang, Yue-Li
    THEORY OF COMPUTING SYSTEMS, 2016, 58 (02) : 345 - 356
  • [2] The Outer-connected Domination Number of Sierpiński-like Graphs
    Shun-Chieh Chang
    Jia-Jie Liu
    Yue-Li Wang
    Theory of Computing Systems, 2016, 58 : 345 - 356
  • [3] THE OUTER-CONNECTED VERTEX EDGE DOMINATION NUMBER OF A TREE
    Krishnakumari, Balakrishna
    Venkatakrishnan, Yanamandram Balasubramanian
    COMMUNICATIONS OF THE KOREAN MATHEMATICAL SOCIETY, 2018, 33 (01): : 361 - 369
  • [4] On the outer-connected domination number for graph products
    Hashemipour, Maliheh
    Hooshmandasl, Mohammad Reza
    Shakiba, Ali
    JOURNAL OF INFORMATION & OPTIMIZATION SCIENCES, 2020, 41 (05) : 1253 - 1267
  • [5] Finding outer-connected dominating sets in interval graphs
    Lin, Chiou-Jiun
    Liu, Jia-Jie
    Wang, Yue-Li
    INFORMATION PROCESSING LETTERS, 2015, 115 (12) : 917 - 922
  • [6] Domination and Outer Connected Domination in Maximal Outerplanar Graphs
    Wei Zhuang
    Graphs and Combinatorics, 2021, 37 : 2679 - 2696
  • [7] Domination and Outer Connected Domination in Maximal Outerplanar Graphs
    Zhuang, Wei
    GRAPHS AND COMBINATORICS, 2021, 37 (06) : 2679 - 2696
  • [8] Algorithm and Hardness Results for Outer-connected Dominating Set in Graphs
    Panda, B. S.
    Pandey, Arti
    ALGORITHMS AND COMPUTATION, WALCOM 2014, 2014, 8344 : 151 - 162
  • [9] Computing a minimum outer-connected dominating set for the class of chordal graphs
    Keil, J. Mark
    Pradhan, D.
    INFORMATION PROCESSING LETTERS, 2013, 113 (14-16) : 552 - 561
  • [10] OUTER CONNECTED DOMINATION IN MAXIMAL OUTERPLANAR GRAPHS AND BEYOND
    Yang, Wei
    Wu, Baoyindureng
    DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2024, 44 (02) : 575 - 590
12345