Bounds on a generalized domination parameter

Abstract

If n is an integer, n ≥ 2 and u and v are vertices of a graph G, then u and v are said to be K_n-adjacent vertices of G if there is a subgraph of G, isomorphic to K_n , containing u and v. For n ≥ 2, a K_n- dominating set of G is a set D of vertices such that every vertex of G belongs to D or is K_n-adjacent to a vertex of D. The K_n-domination number γK_n (G) of G is the minimum cardinality among the K_n-dominating sets of vertices of G. It is shown that, for n ε {3,4}, if G is a graph of order p with no K_n-isolated vertex, then γK_n (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.