Partial Domination in Prisms of Graphs

Abstract

For any graph G = (V, E) and proportion $p\in (0,1]$, a set $S\subseteq V$ is a p-dominating set if $\frac{|N[S]|}{|V|}\ge p$. The $p$-domination number ${\gamma }_p(G)$ equals the minimum cardinality of a $p$-dominating set in G. For a permutation $\pi$ of the vertex set of G, the graph $\pi$G is obtained from two disjoint copies $G_1$ and $G_2$ of $G$ by joining each v in $G_1$ to $\pi (v)$ in $G_2$. i.e., $V(\pi G)=V(G_1)\cup V(G_2)\text{ and }E(G)=E(G_1)\cup E(G_2)\cup \{\{v,\pi (v)\}:v\in V(G_1),\pi (v)\in V(G_2)\}$. The graph $\pi G$ is called the prism of $G$ with respect to $\pi$. In this paper, we find some relations between the domination and the $p$-domination numbers in the context of graph and its prism graph for particular values of $p$.

8 pages