Article ID Journal Published Year Pages File Type
4646595 Discrete Mathematics 2016 6 Pages PDF
Abstract

As a common generalization of the domination number and the total domination number of a graph GG, we study the kk-component domination number γk(G)γk(G) of GG defined as the minimum cardinality of a dominating set DD of GG for which each component of the subgraph G[D]G[D] of GG induced by DD has order at least kk.We show that for every positive integer kk, and every graph GG of order nn at least k+1k+1 and without isolated vertices, we have γk(G)≤knk+1. Furthermore, we characterize all extremal graphs. We propose two conjectures concerning graphs of minimum degree 22, and prove a related result.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, , ,