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 条
  • [41] Vertex-edge domination in graphs
    Boutrig, Razika
    Chellali, Mustapha
    Haynes, Teresa W.
    Hedetniemi, Stephen T.
    AEQUATIONES MATHEMATICAE, 2016, 90 (02) : 355 - 366
  • [42] On the Global Double Roman Domination of Graphs
    Guoliang Hao
    Xiaodan Chen
    Bulletin of the Malaysian Mathematical Sciences Society, 2020, 43 : 3007 - 3018
  • [43] Vertex-edge domination in graphs
    Razika Boutrig
    Mustapha Chellali
    Teresa W. Haynes
    Stephen T. Hedetniemi
    Aequationes mathematicae, 2016, 90 : 355 - 366
  • [44] Domination dot-critical graphs
    Burton, T
    Sumner, DP
    DISCRETE MATHEMATICS, 2006, 306 (01) : 11 - 18
  • [45] The algorithmic complexity of mixed domination in graphs
    Zhao, Yancai
    Kang, Liying
    Sohn, Moo Young
    THEORETICAL COMPUTER SCIENCE, 2011, 412 (22) : 2387 - 2392
  • [46] Algorithmic aspect of stratified domination in graphs
    Chang, Gerard Jennhwa
    Chang, Chan-Wei
    Kuo, David
    Poon, Sheung-Hung
    INFORMATION PROCESSING LETTERS, 2013, 113 (22-24) : 861 - 865
  • [47] Domination in some subclasses of bipartite graphs
    Pandey, Arti
    Panda, B. S.
    DISCRETE APPLIED MATHEMATICS, 2019, 252 : 51 - 66
  • [48] On the Global Double Roman Domination of Graphs
    Hao, Guoliang
    Chen, Xiaodan
    BULLETIN OF THE MALAYSIAN MATHEMATICAL SCIENCES SOCIETY, 2020, 43 (04) : 3007 - 3018
  • [49] Relating the total {2}-domination number with the total domination number of graphs
    Villamar, I. Rios
    Cabrera-Martinez, A.
    Sanchez, J. L.
    Sigarreta, J. M.
    DISCRETE APPLIED MATHEMATICS, 2023, 333 : 90 - 95
  • [50] A general method in the theory of domination in graphs
    Hansberg, Adriana
    Meierling, Dirk
    Volkmann, Lutz
    INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS, 2010, 87 (13) : 2915 - 2924
12345