Lower bounds on the distance domination number of a graph

Randy Davila; Caleb Fast; Michael A. Henning; Franklin Kenter

Lower bounds on the distance domination number of a graph

Randy Davila
, Caleb Fast
, Michael A. Henning
, Franklin Kenter

Mathematics and Applied Mathematics

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

12 Citations (Scopus)

Abstract

For an integer k ≥ 1, a (distance) k-dominating set of a connected graph G is a set S of vertices of G such that every vertex of V (G) \ S is at distance at most k from some vertex of S. The kdomination number, γ_k(G), of G is the minimum cardinality of a kdominating set of G. In this paper, we establish lower bounds on the k-domination number of a graph in terms of its diameter, radius, and girth. We prove that for connected graphs G and H, γ_k(G × H) ≥ γ_k(G) + γ_k(H) − 1, where G × H denotes the direct product of G and H.

Original language	English
Pages (from-to)	11-21
Number of pages	11
Journal	Contributions to Discrete Mathematics
Volume	12
Issue number	2
Publication status	Published - 2017

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics

Cite this

@article{c0b5e19721b741968e5e5954aaad044d,

title = "Lower bounds on the distance domination number of a graph",

abstract = "For an integer k ≥ 1, a (distance) k-dominating set of a connected graph G is a set S of vertices of G such that every vertex of V (G) \textbackslash{} S is at distance at most k from some vertex of S. The kdomination number, γk(G), of G is the minimum cardinality of a kdominating set of G. In this paper, we establish lower bounds on the k-domination number of a graph in terms of its diameter, radius, and girth. We prove that for connected graphs G and H, γk(G × H) ≥ γk(G) + γk(H) − 1, where G × H denotes the direct product of G and H.",

author = "Randy Davila and Caleb Fast and Henning, \{Michael A.\} and Franklin Kenter",

note = "Publisher Copyright: {\textcopyright} 2017 University of Calgary.",

year = "2017",

language = "English",

volume = "12",

pages = "11--21",

journal = "Contributions to Discrete Mathematics",

issn = "1715-0868",

publisher = "University of Calgary Press",

number = "2",

}

TY - JOUR

T1 - Lower bounds on the distance domination number of a graph

AU - Davila, Randy

AU - Fast, Caleb

AU - Henning, Michael A.

AU - Kenter, Franklin

PY - 2017

Y1 - 2017

N2 - For an integer k ≥ 1, a (distance) k-dominating set of a connected graph G is a set S of vertices of G such that every vertex of V (G) \ S is at distance at most k from some vertex of S. The kdomination number, γk(G), of G is the minimum cardinality of a kdominating set of G. In this paper, we establish lower bounds on the k-domination number of a graph in terms of its diameter, radius, and girth. We prove that for connected graphs G and H, γk(G × H) ≥ γk(G) + γk(H) − 1, where G × H denotes the direct product of G and H.

AB - For an integer k ≥ 1, a (distance) k-dominating set of a connected graph G is a set S of vertices of G such that every vertex of V (G) \ S is at distance at most k from some vertex of S. The kdomination number, γk(G), of G is the minimum cardinality of a kdominating set of G. In this paper, we establish lower bounds on the k-domination number of a graph in terms of its diameter, radius, and girth. We prove that for connected graphs G and H, γk(G × H) ≥ γk(G) + γk(H) − 1, where G × H denotes the direct product of G and H.

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

M3 - Article

AN - SCOPUS:85036526882

SN - 1715-0868

VL - 12

SP - 11

EP - 21

JO - Contributions to Discrete Mathematics

JF - Contributions to Discrete Mathematics

IS - 2

ER -

Lower bounds on the distance domination number of a graph

Abstract

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this