An upper bound on the paired-domination number in terms of the number of edges in the graph

被引：2
作者：
Henning, Michael A. [1 ]
机构：
[1] Univ Johannesburg, Dept Math, ZA-2006 Johannesburg, South Africa
来源：
DISCRETE MATHEMATICS | 2010年 / 310卷 / 21期
基金：
新加坡国家研究基金会;
关键词：
Bounds; Paired domination; Minimum degree 2; Size; TREES;
D O I：
10.1016/j.disc.2010.06.033
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
In this paper, we continue the study of paired domination in graphs introduced by Haynes and Slater [T.W. Haynes, P.J. Slater, Paired-domination in graphs, Networks 32 (1998) 199-206]. A paired-dominating set of a graph is a dominating set whose induced subgraph contains a perfect matching. The paired-domination number of a graph G, denoted by gamma(pr)(G), is the minimum cardinality of a paired-dominating set in C. We show that if G is a connected graph of size m >= 18 with minimum degree at least 2, then gamma(pr)(G) <= 4m/7 and we characterize the (infinite family of) graphs that achieve equality in this bound. (C) 2010 Elsevier B.V. All rights reserved.
引用
收藏
页码：2847 / 2857
页数：11
相关论文
共 26 条
  • [1] Bresar B, 2007, UTILITAS MATHEMATICA, V73, P255
  • [2] Chellali M, 2005, UTILITAS MATHEMATICA, V67, P161
  • [3] Chellali M, 2004, ARS COMBINATORIA, V73, P3
  • [4] Chellali M., 2004, AKCE Int. J. Graphs Comb, V1, P69
  • [5] Upper bounds on the paired-domination number
    Chen, Xue-gang
    Shiu, Wai Chee
    Chan, Wai Hong
    [J]. APPLIED MATHEMATICS LETTERS, 2008, 21 (11) : 1194 - 1198
  • [6] [陈学刚 Chen Xuegang], 2007, [数学物理学报, Acta Mathematica Scientia], V27, P166
  • [7] Paired domination on interval and circular-arc graphs
    Cheng, T. C. E.
    Kang, L. Y.
    Ng, C. T.
    [J]. DISCRETE APPLIED MATHEMATICS, 2007, 155 (16) : 2077 - 2086
  • [8] A polynomial-time algorithm for the paired-domination problem on permutation graphs
    Cheng, T. C. E.
    Kang, Liying
    Shan, Erfang
    [J]. DISCRETE APPLIED MATHEMATICS, 2009, 157 (02) : 262 - 271
  • [9] Paired-domination in P5-free graphs
    Dorbec, Paul
    Gravier, Sylvain
    [J]. GRAPHS AND COMBINATORICS, 2008, 24 (04) : 303 - 308
  • [10] Paired-domination in generalized claw-free graphs
    Dorbec, Paul
    Gravier, Sylvain
    Henning, Michael A.
    [J]. JOURNAL OF COMBINATORIAL OPTIMIZATION, 2007, 14 (01) : 1 - 7
123