Upper Bounds for α-Domination Parameters

被引：11

作者：

Gagarin, Andrei ^{[1
]}

Poghosyan, Anush ^{[2
]}

Zverovich, Vadim ^{[2
]}

机构：

[1] Acadia Univ, Dept Math & Stat, Wolfville, NS B4P 2R6, Canada

[2] Univ W England, Dept Math & Stat, Bristol BS16 1QY, Avon, England

来源：

GRAPHS AND COMBINATORICS | 2009年 / 25卷 / 04期

关键词：

Graph; Domination; alpha-Domination; alpha-Rate domination; Probabilistic method; K-TUPLE DOMINATION; GRAPHS; NETWORKS; NUMBER;

D O I：

10.1007/s00373-009-0864-6

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

We provide a new upper bound for the alpha-domination number in terms of a parameter alpha, 0 < alpha a parts per thousand currency sign 1, and graph vertex degrees. This result generalises the well-known Caro-Roditty bound for the domination number of a graph. The same probabilistic construction is used to generalise another well-known upper bound for the classical domination in graphs. Using a different probabilistic construction, we prove similar upper bounds for the alpha-rate domination number, which combines the concepts of alpha-domination and k-tuple domination.

引用

页码：513 / 520

页数：8

共 16 条

[1] Experiments on data reduction for optimal domination in networks [J].

Alber, Jochen ;

Betzler, Nadja ;

Niedermeier, Rolf .

ANNALS OF OPERATIONS RESEARCH, 2006, 146 (1) :105-117

[2]

Alon Noga, 1992, The Probabilistic Method

[3]

Arnautov V.I., 1974, Prikl. Mat. i Prog, V11, P3

[4] Dominating a family of graphs with small connected subgraphs [J].

Caro, Y ;

Yuster, R .

COMBINATORICS PROBABILITY & COMPUTING, 2000, 9 (04) :309-313

[5] Lower Bounds and Algorithms for Dominating Sets in Web Graphs [J].

Cooper, Colin ;

Klasing, Ralf ;

Zito, Michele .

INTERNET MATHEMATICS, 2005, 2 (03) :275-300

[6] α-Domination perfect trees [J].

Dahme, F. ;

Rautenbach, D. ;

Volkmann, L. .

DISCRETE MATHEMATICS, 2008, 308 (15) :3187-3198

[7] On constructing k-connected k-dominating set in wireless ad hoc and sensor networks [J].

Dai, Fei ;

Wu, Jie .

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING, 2006, 66 (07) :947-958

[8] α-Domination [J].

Dunbar, JE ;

Hoffman, DG ;

Laskar, RC ;

Markus, LR .

DISCRETE MATHEMATICS, 2000, 211 (1-3) :11-26

[9] ON A CONJECTURE OF FINK AND JACOBSON CONCERNING KAPPA-DOMINATION AND KAPPA-DEPENDENCE [J].

FAVARON, O .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1985, 39 (01) :101-102

[10] On k-domination and minimum degree in graphs [J].

Favaron, Odile ;

Hansberg, Adriana ;

Volkmann, Lutz .

JOURNAL OF GRAPH THEORY, 2008, 57 (01) :33-40

← 1 2 →