A note on the k-domination number of a graph (Q919005): Difference between revisions

The k-domination number of a graph \(G=G(V,E),\) \(c_ k(G)\), is the least cardinality of a set \(X\subset V\) such that any vertex in \(V\setminus X\) is adjacent to at least k vertices of X. The authors prove the following theorem: Let n, k be positive integers. If the minimum degree of vertices in the graph \(G(V,E)\geq ((n+1)/k)k-1,\) then \(c_ k(G)\leq n| V| /(n+1)\).