Bounds on the k-domination number of a graph

Ermelinda Delaviña; Wayne Goddard; Michael A. Henning; Ryan Pepper; Emil R. Vaughan

doi:10.1016/j.aml.2011.01.013

Bounds on the k-domination number of a graph

Ermelinda Delaviña
, Wayne Goddard
, Michael A. Henning
, Ryan Pepper
, Emil R. Vaughan

Mathematics and Applied Mathematics

Research output: Contribution to journal › Article › peer-review

25 Citations (Scopus)

Abstract

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 any graph with minimum degree at least 2k-1, the k-domination number is at most the matching number.

Original language	English
Pages (from-to)	996-998
Number of pages	3
Journal	Applied Mathematics Letters
Volume	24
Issue number	6
DOIs	https://doi.org/10.1016/j.aml.2011.01.013
Publication status	Published - Jun 2011

Keywords

Graph
Independence number
Matching number
k-domination

ASJC Scopus subject areas

Applied Mathematics

Access to Document

10.1016/j.aml.2011.01.013

Cite this

@article{3807faf70be34e4ebc274ec87a5a75df,

title = "Bounds on the k-domination number of a graph",

abstract = "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 any graph with minimum degree at least 2k-1, the k-domination number is at most the matching number.",

keywords = "Graph, Independence number, Matching number, k-domination",

author = "Ermelinda Delavi{\~n}a and Wayne Goddard and Henning, \{Michael A.\} and Ryan Pepper and Vaughan, \{Emil R.\}",

year = "2011",

month = jun,

doi = "10.1016/j.aml.2011.01.013",

language = "English",

volume = "24",

pages = "996--998",

journal = "Applied Mathematics Letters",

issn = "0893-9659",

publisher = "Elsevier Ltd.",

number = "6",

}

TY - JOUR

T1 - Bounds on the k-domination number of a graph

AU - Delaviña, Ermelinda

AU - Goddard, Wayne

AU - Henning, Michael A.

AU - Pepper, Ryan

AU - Vaughan, Emil R.

PY - 2011/6

Y1 - 2011/6

N2 - 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 any graph with minimum degree at least 2k-1, the k-domination number is at most the matching number.

AB - 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 any graph with minimum degree at least 2k-1, the k-domination number is at most the matching number.

KW - Graph

KW - Independence number

KW - Matching number

KW - k-domination

UR - https://www.scopus.com/pages/publications/79952428227

U2 - 10.1016/j.aml.2011.01.013

DO - 10.1016/j.aml.2011.01.013

M3 - Article

AN - SCOPUS:79952428227

SN - 0893-9659

VL - 24

SP - 996

EP - 998

JO - Applied Mathematics Letters

JF - Applied Mathematics Letters

IS - 6

ER -

Bounds on the k-domination number of a graph

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this