Lower bounds on the distance domination number of a graph

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

Research output: Contribution to journalArticlepeer-review

9 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 languageEnglish
Pages (from-to)11-21
Number of pages11
JournalContributions to Discrete Mathematics
Volume12
Issue number2
Publication statusPublished - 2017

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics

Fingerprint

Dive into the research topics of 'Lower bounds on the distance domination number of a graph'. Together they form a unique fingerprint.

Cite this