B-Packing Sets in Graphs

Abstract

A set $S\subseteq V$ is $\alpha$-dominating if for all $v\in V–S$, $|N(v)\cap S|\ge \alpha |N(v)|$. The $\alpha$-domination number of $G$ equals the minimum cardinality of an $\alpha$-dominating set $S$ in $G$. Since being introduced by Dunbar et al. in 2000, $\alpha$-domination has been studied for various graphs and a variety of bounds have been developed.

In this paper, we propose a new parameter derived by flipping the inequality in the definition of $\alpha$-domination. We say a set $S\subset V$ is a $\beta$-packing set of a graph $G$ if $S$ is a proper, maximal set having the property that for all vertices $v\in V–S$, $|N(v)\cap S|\le \beta |N(v)|$ for some $0<\beta \le 1$. The $\beta$-\emph{packing number} of $G$, denoted $\beta \text{-pack}(G)$, equals the maximum cardinality of a $\beta$-packing set in $G$.

In this research, we determine $\beta \text{-pack}(G)$ for several classes of graphs, and we explore some properties of $\beta$-packing sets.