A lower bound for the distance \(k\)-domination number of trees (Q2581114)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 2246302
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | A lower bound for the distance \(k\)-domination number of trees |
scientific article; zbMATH DE number 2246302 |
Statements
A lower bound for the distance \(k\)-domination number of trees (English)
0 references
13 January 2006
0 references
The distance \(k\)-domination number \(\gamma_k(G)\) of a graph \(G\) is the size of the smallest subset \(D\) of nodes of \(G\) such that any node not in \(D\) has distance at most \(k\) from at least one node in \(D\). The authors show that if \(T\) is a tree with \(n\) nodes and \(t\) end-nodes, then \((2k+1)\gamma_k(T)\geq n+2k-kt\); and they characterize the trees for which equality holds.
0 references
0.9416710138320924
0 references
0.8438833355903625
0 references
0.8348363041877747
0 references
0.8286571502685547
0 references
