Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4646595 | Discrete Mathematics | 2016 | 6 Pages |
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.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
José D. Alvarado, Simone Dantas, Dieter Rautenbach,