Partial Domination in Graphs

Abstract

Let $G=(V,E)$ be a graph. For some $\alpha$ with $0<\alpha \le 1$, a subset $S$ of $V$ is said to be a $\alpha$-partial dominating set if $|N[S]|\ge \alpha |V|$. The size of a smallest such $S$ is called the $\alpha$-partial domination number and is denoted by ${\mathsf{pd}}_{\alpha }(G)$. In this paper, we introduce $\alpha$-partial domination number in a graph $G$ and study different bounds on the partial domination number of a graph $G$ with respect to its order, maximum degree, domination number etc., Moreover, $\alpha$-partial domination spectrum is introduced and Nordhaus-Gaddum bounds on the partial domination number are studied.

11 pages

References in corpus (2)

• Partial Domination in Graphs
• Partial Domination in Graphs

Cited by in corpus (3)

• Partial Domination in Graphs
• Optimal Metric Search Is Equivalent to the Minimum Dominating Set Problem
• Properties of Partial Dominating Sets of Graphs