Journal of Combinatorics

Volume 13 (2022)

Number 4

Small domination-type invariants in random graphs

Pages: 531 – 543

DOI: https://dx.doi.org/10.4310/JOC.2022.v13.n4.a4

Authors

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)

Abstract

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$.

Keywords

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

2010 Mathematics Subject Classification

Primary 05C69. Secondary 05C80.

Received 19 November 2019

Accepted 11 August 2021

Published 18 August 2022