SAMS Subject Classification Number: 6

A set $X\subseteq V$ is a dominating set of a graph $G=(V,E)$ if every vertex in $V\setminus X$ is adjacent to a vertex in $X$. The domination number of $G$ is the cardinality of the smallest dominating set of $G$. We study the distribution of the domination number in a conditioned Galton-Watson model with offspring distribution $\xi$ that satisfies $\mathbb{E}\xi =1$ and $0<\mathrm{Var}\xi <\mathrm{\infty }$. Given a discrete random variable $\xi$ with support on $\{0,1,2,\dots \}$, the Galton-Watson tree $\mathcal{T}$ with offspring distribution $\xi$ is the random tree generated in the following way: we start with a root and generate a number of children according to $\xi$. For each of the children of the root, generate a number of children of their own according to $\xi$ independently of the other vertices. Then, we repeat this process until it stops. Now, we consider the model ${\mathcal{T}}_n$ which is the above random tree conditioned to have exactly $n$ vertices. We show that the domination number in such a random tree is asymptotically normal as the order of the tree tends to infinity. Our method is based on the analysis of the Cockayne-Goodman-Hedetniemi (CGH) algorithm [1,2] and a recent extension of Janson’s result on local additive functionals [3]. In fact, the CGH algorithm leads to a finite tree partitioning that allows to construct the additive functional which will be then used to prove our result according to [4], an extension of Janson’s result. We also prove that the same result holds for the distribution of the total domination number, i.e., the cardinality of the smallest total dominating set of $G$. The later is defined similarly as the dominating set by replacing $V\setminus X$ to $V$. We will discuss these results and their proofs in this talk.

[1] E. Cockayne, S. Goodman, and S. Hedetniemi. A linear algorithm for the domination number

of a tree. Information Processing Letters, 4(2):41–44, 1975.
[2] E. J. Cockayne, R. M. Dawes, and S. T. Hedetniemi. Total domination in graphs. Networks, 10:211–219, 1980.

[3] S. Janson. Asymptotic normality of fringe subtrees and additive functionals in conditioned galton watson trees. Random Structures Algorithms, 48(1):57–101, 2016.

[4] D. Ralaivaosaona, M. Śileikis, and S. Wagner. A central limit theorem for almost local additive tree functionals. Algorithmica, 82(3):642–679, 2020.