Forcing Full Domination in Graphs

Abstract

For each vertex $v$ in a graph $G$, let there be associated a particular type of a subgraph $F_v$ of $G$. In this context, the vertex $v$ is said to dominate $F_v$. A set $S$ of vertices of $G$ is called a full dominating set if every vertex of $G$ belongs to a subgraph $F_v$ of $G$ for some $v\in S$ and every edge of $G$ belongs to a subgraph $F_w$ of $G$ for some $w\in S$. The minimum cardinality of a full dominating set of $G$ is its full domination number ${\gamma }_F(G)$. A full dominating set of $G$ of cardinality ${\gamma }_F(G)$ is called a ${\gamma }_F$-set of $G$.

We study three types of full domination in graphs: full star domination, where $F_v$ is the maximum star centered at $v$; full closed domination, where $F_v$ is the subgraph induced by the closed neighborhood of $v$; and full open domination, where $F_v$ is the subgraph induced by the open neighborhood of $v$.

A subset $T$ of a ${\gamma }_F$-set $S$ in a graph $G$ is a forcing subset for $S$ if $S$ is the unique ${\gamma }_F$-set containing $T$. The forcing full domination number of $S$ in $G$ is the minimum cardinality of a forcing subset for $S$, and the forcing full domination number $f_{{\gamma }_F}(G)$ of the graph $G$ is the minimum forcing full domination number among all ${\gamma }_F$-sets of $G$.

We present several realization results concerning forcing parameters in full domination.