Some results on Kr-covered graphs

Abstract

A graph G is K_r-covered if every vertex of G is contained in a K_r, i.e., in a complete subgraph on r vertices. Two vertices of a graph G are said to be K_r-adjacent if there is a K_r in G containing them both. A set of vertices D in a K_r-covered graph G is a K_r-dominating set if every vertex of G either belongs to D or is K_r-adjacent to a vertex of D. The K_r-domination number _γKr(G) is the size of any smallest K_r-dominating set in G. In this paper, we study properties of K_r-covered graphs. In particular, we obtain a new and much shorter proof of an upper bound first obtained by Henning and Swart [HS] for the K₄-domination number of a K₄-covered graph and obtain a new bound for the K₅-domination number of a K₅-covered graph in which the maximum degree does not exceed 7.