The upper bound on k-tuple domination numbers of graphs

被引:14
作者
Chang, Gerard J. [1 ,2 ,3 ]
机构
[1] Natl Taiwan Univ, Dept Math, Taipei 10617, Taiwan
[2] Natl Taiwan Univ, Inst Math Sci, Taipei 10617, Taiwan
[3] Natl Ctr Theoret Sci, Taipei Off, Taipei, Taiwan
关键词
D O I
10.1016/j.ejc.2007.05.009
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
In a graph G, a vertex is said to dominate itself and all vertices adjacent to it. For a positive integer k, the k-tuple domination number gamma xk (G) of G is the minimum size of a subset D of V (G) such that every vertex in G is dominated by at least k vertices in D. To generalize/improve known upper bounds for the k-tuple domination number, this paper establishes that for any positive integer k and any graph G of n vertices and minimum degree delta, (gamma x k)(G) <= In(delta-k+2) + In (d) over tilde (k-1) + 1/ delta - k + 2 n, where (d) over tilde (m) = 1/n [GRAPHICS] with d(i) the degree of ith vertex of G. (c) 2007 Elsevier Ltd. All rights reserved.
引用
收藏
页码:1333 / 1336
页数:4
相关论文
共 15 条
[1]  
ALON A, 2000, PROBABILITY METHOD
[2]  
ARNAUTOV VI, 1974, PRIKL MATH PROGRAMM, V11, P38
[3]  
Chang G. J., 1998, HDB COMBINATORIAL OP, V3, P339
[4]  
GAGARIN A, UNPUB GEN UPPER BOUN
[5]  
Harant J., 2005, DISCUSS MATH GRAPH T, V25, P29, DOI DOI 10.7151/DMGT.1256
[6]   Nordhaus-Gaddum inequalities for domination in graphs [J].
Harary, F ;
Haynes, TW .
DISCRETE MATHEMATICS, 1996, 155 (1-3) :99-105
[7]  
Harary F, 2000, ARS COMBINATORIA, V55, P201
[8]  
Haynes T.W., 1998, FUNDAMENTALS DOMINAT
[9]  
Haynes TW, 1998, DOMINATION GRAPHS TH
[10]   Hardness results and approximation algorithms of k-tuple domination in graphs [J].
Klasing, R ;
Laforest, C .
INFORMATION PROCESSING LETTERS, 2004, 89 (02) :75-83