If n is an integer, n ≥ 2 anduand v are vertices of a graph G, then u andvare said to be Kn-adjacent vertices of G if there is a subgraph of G, isomorphic toKn, containing u andv.For n ≥ 2, aKn-dominating set of G is a setDof vertices such that every vertex of G belongs toDor is Kn-adjacent to a vertex ofD.TheKn-domination number γKn(G) of G is the minimum cardinality among the Kn-dominating sets of vertices ofG.It is shown that, for n ε {3,4}, ifGis a graph of order p with no Kn-isolated vertex, then γKn(G) ≤p/n.We establish that this is a best possible upper bound. It is shown that the result is not true for n ≥ 5.
展开▼