Bounds on the Upper $k$-Domination Number and the Upper $k$-Star-Forming Number of a Graph

Abstract

A subset $A$ of vertices of a graph $G$ is a $k$-dominating set if every vertex not in $A$ has at least $k$ neighbors in $A$ and a $k$-star-forming set if every vertex not in $A$ forms with $k$ vertices of $A$ a not necessarily induced star $K_{1,k}$. The maximum cardinalities of a minimal $k$-dominating set and of a minimal $k$-star-forming set of $G$ are respectively denoted by ${\mathrm{\Gamma }}_k(G)$ and ${\text{SF}}_k(G)$. We determine upper bounds on ${\mathrm{\Gamma }}_k(G)$ and ${\text{SF}}_k(G)$ and describe the structure of the extremal graphs attaining them.