Journal of Combinatorics

Volume 13 (2022)

Number 4

Small domination-type invariants in random graphs

Pages: 531 – 543



Michitaka Furuya (College of Liberal Arts and Sciences, Kitasato University, Sagamihara, Kanagawa, Japan)

Tamae Kawasaki (Department of Applied Mathematics, Tokyo University of Science, Shinjuku-ku, Tokyo, Japan)


For $c \in \mathbb{R}^+ \cup {\lbrace \infty \rbrace}$ and a graph $G$, a function $f : V (G) \to {\lbrace 0, 1 , c \rbrace}$ is called a $c$-self dominating function of $G$ if for every vertex $u \in V (G), f(u) \geq c$ or $\operatorname{max} {\lbrace f(v) : v \in N_G (u) \rbrace} \geq 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 investigate a behavior of the $c$-self domination number in random graphs for small $c$.


domination number, random graph, self domination number, Roman domination number, differential

2010 Mathematics Subject Classification

Primary 05C69. Secondary 05C80.

The work of Michitaka Furuya was supported by JSPS KAKENHI Grant number JP18K13449.

Received 19 November 2019

Accepted 11 August 2021

Published 18 August 2022