Abstract | ||
---|---|---|
As a common generalization of the domination number and the total domination number of a graph G , we study the k -component domination number γ k ( G ) of G defined as the minimum cardinality of a dominating set D of G for which each component of the subgraph G D of G induced by D has order at least k .We show that for every positive integer k , and every graph G of order n at least k + 1 and without isolated vertices, we have γ k ( G ) ź k n k + 1 . Furthermore, we characterize all extremal graphs. We propose two conjectures concerning graphs of minimum degree 2 , and prove a related result. |
Year | DOI | Venue |
---|---|---|
2016 | 10.1016/j.disc.2016.05.016 | Discrete Mathematics |
Keywords | Field | DocType |
Domination,Total domination | Integer,Discrete mathematics,Graph,Dominating set,Combinatorics,Vertex (geometry),Cardinality,Domination analysis,Mathematics | Journal |
Volume | Issue | ISSN |
339 | 11 | 0012-365X |
Citations | PageRank | References |
0 | 0.34 | 6 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
José D. Alvarado | 1 | 7 | 3.82 |
Simone Dantas | 2 | 119 | 24.99 |
Dieter Rautenbach | 3 | 946 | 138.87 |