Bounds on the k-domination number of a graph

被引：22

作者：

DeLaVina, Ermelinda ^{[1
]}

Goddard, Wayne ^{[2
]}

Henning, Michael A. ^{[3
]}

Pepper, Ryan ^{[1
]}

Vaughan, Emil R. ^{[4
]}

机构：

[1] Univ Houston Downtown, Houston, TX 77002 USA

[2] Clemson Univ, Clemson, SC 29631 USA

[3] Univ Johannesburg, Johannesburg, South Africa

[4] Univ London, London WC1E 7HU, England

来源：

APPLIED MATHEMATICS LETTERS | 2011年 / 24卷 / 06期

基金：

新加坡国家研究基金会;

关键词：

k-domination; Matching number; Independence number; Graph;

D O I：

10.1016/j.aml.2011.01.013

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

The k-domination number of a graph is the cardinality of a smallest set of vertices such that every vertex not in the set is adjacent to at least k vertices of the set. We prove two bounds on the k-domination number of a graph, inspired by two conjectures of the computer program Graffiti.pc. In particular, we show that for ally graph with minimum degree at least 2k - 1, the k-domination number is at most the matching number. (C) 2011 Elsevier Ltd. All rights reserved.

引用

页码：996 / 998

页数：3

共 11 条

[1]

[Anonymous], 2010, C NUMER

[2]

Bondy J.A., 2008, GTM

[3]

Caro Y., 1990, INT J MATH MATH SCI, V13, P205, DOI [10.1155/S016117129000031X, DOI 10.1155/S016117129000031X, 10.1155S016117129000031X////]

[4]

COCKAYNE EJ, 1978, LECT NOTES MATH, V642, P141, DOI DOI 10.1007/BFB0070371

[5]

DELAVINA E, WRITTEN WALL, V2

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

Favaron, Odile ;

Hansberg, Adriana ;

Volkmann, Lutz .

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

[7]

Fink J.F., 1985, Graph Theory with Applications to Algorithms and Computer Science, P283

[8]

Fujisawa J, 2008, AUSTRALAS J COMB, V40, P265

[9]

Hansberg A., 2009, THESIS RWTH AACHEN U

[10]

Pepper R., 2010, C NUMER, V206, P65

← 1 2 →