Upper total domination versus upper paired-domination

被引:13
作者
Dorbec, Paul [1 ,2 ]
Henning, Michael A. [1 ]
McCoy, John [1 ]
机构
[1] Univ KwaZulu Natal, Sch Math Sci, ZA-3209 Pietermaritzburg, South Africa
[2] Univ Grenoble 1, Lab Leibniz, F-38031 Grenoble, France
基金
新加坡国家研究基金会;
关键词
bounds; upper total domination; upper paired-domination;
D O I
10.2989/160736007780205693
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
Let G be a, graph with no isolated vertices. A set S of vertices in G is a total dominating set of G if every vertex of G is adjacent to some vertex in S, while a paired-dominating set of G is a dominating set of vertices whose induced subgraph has a perfect matching. The maximum cardinality of a minimal total dominating set and a minimal paired-dominating set of G is the upper total domination number and upper paired-domination number of G, respectively, denoted by Gamma(t)(G) and Gamma(pr)(G). In this paper, we investigate the relationship between the upper total domination and upper paired-domination numbers of a graph. We show that for every graph G with no isolated vertex Gamma(t)(G) >= 1/2 (Gamma(pr) (G) + 2), and we characterize the trees achieving this bound. For each positive integer k., we observe that there exist, connected graphs G and H such that Gamma(pr)(G) - Gamma(t)(G) >= k and Gamma(t)(H) - Gamma(pr)(H) >= k. However for the family of trees T on at least two vertices, we show that Gamma(t)(T) <= Gamma(pr) (T).
引用
收藏
页码:1 / 12
页数:12
相关论文
共 19 条
  • [1] [Anonymous], DISCUSS MATH GRAPH T
  • [2] Some remarks on domination
    Archdeacon, D
    Ellis-Monaghan, J
    Fisher, D
    Froncek, D
    Lam, PCB
    Seager, S
    Wei, B
    Yuster, R
    [J]. JOURNAL OF GRAPH THEORY, 2004, 46 (03) : 207 - 210
  • [3] Chellali M, 2005, UTILITAS MATHEMATICA, V67, P161
  • [4] Chellali M, 2004, ARS COMBINATORIA, V73, P3
  • [5] Chellali M., 2004, AKCE Int. J. Graphs Comb, V1, P69
  • [6] TOTAL DOMINATION IN GRAPHS
    COCKAYNE, EJ
    DAWES, RM
    HEDETNIEMI, ST
    [J]. NETWORKS, 1980, 10 (03) : 211 - 219
  • [7] Paired-domination in claw-free cubic graphs
    Favaron, O
    Henning, MA
    [J]. GRAPHS AND COMBINATORICS, 2004, 20 (04) : 447 - 456
  • [8] Upper total domination in claw-free graphs
    Favaron, O
    Henning, MA
    [J]. JOURNAL OF GRAPH THEORY, 2003, 44 (02) : 148 - 158
  • [9] Haynes T. W., 1998, FUNDAMENTALS DOMINAT
  • [10] Haynes T.W., 1998, FUNDAMENTALS DOMINAT