On $k$-star-forming Sets in Graphs

Abstract

In [10], Fink and Jacobson gave a generalization of the concepts of domination and independence in graphs which extends only partially the well-known inequality chain $\gamma (G)\le i(G)\le \beta (G)\le \mathrm{\Gamma }(G)$ between the usual parameters of domination and independence. If a $k$-independent set is defined as a subset of vertices inducing in $G$ a subgraph of maximum degree less than $k$, we introduce the property which makes a $k$-independent set maximal. This leads us to the notion of a $k$-star-forming set. The corresponding parameters $s{f}_k(G)$ and ${\text{SF}}_k(G)$ satisfy $s{f}_k(G)\le i_k(G)\le {\beta }_k(G)\le {\text{SF}}_k(G)$ where $i_k(G)$ and ${\beta }_k(G)$ are respectively the minimum and the maximum cardinality of a maximal $k$-independent set. We initiate the study of $s{f}_k(G)$ and ${\text{SF}}_k(G)$ and give some results in particular classes of graphs such as trees, chordal graphs, and $K_{1,r}$-free graphs.