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 <\infty\). Given a discrete random variable \(\xi\) with support on \(\{0, 1, 2, \ldots\}\), 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.