Small domination-type invariants in random graphs

Abstract

For $c\in {\mathbb{R}}^{+}\cup \{\infty \}$ and a graph $G$, a function $f:V(G)\to \{0,1,c\}$ is called a $c$-self dominating function of $G$ if for every vertex $u\in V(G)$, $f(u)\ge c$ or $\max \{f(v):v\in N_G(u)\}\ge 1$ where $N_G(u)$ is the neighborhood of $u$ in $G$. The minimum weight $w(f)={\sum }_{u\in V(G)}f(u)$ of a $c$-self dominating function $f$ of $G$ is called the $c$-self domination number of $G$. The $c$-self domination concept is a common generalization of three domination-type invariants; (original) domination, total domination and Roman domination. In this paper, we study a behavior of the $c$-self domination number in random graphs for small $c$.

9 pages, 0 figure