Paired domination in trees: A linear algorithm and asymptotic normality

2025/05/23 by Henning, Michael A., Ralaivaosaona, Dimbinaina
#05C69 #60C05 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2505.17672

Abstract

A set S of vertices in a graph G is a paired dominating set if every vertex of G is adjacent to a vertex in S and the subgraph induced by S contains a perfect matching (not necessarily as an induced subgraph). The paired domination number, γ_pr(G), of G is the minimum cardinality of a paired dominating set of G. We present a linear algorithm for computing the paired domination number of a tree. As an application of our algorithm, we prove that the paired domination number is asymptotically normal in a random rooted tree of order n generated by a conditioned Galton-Watson process as n→∞. In particular, we have found that the paired domination number of a random Cayley tree of order n, where each tree is equally likely, is asymptotically normal with expectation approaching (0.5177…)n.

Citations

• A note on the independence number, domination number and related\n parameters of random binary search trees and random recursive trees
• Asymptotic normality of fringe subtrees and additive functionals in conditioned Galton--Watson trees
• Simply generated trees, conditioned Galton--Watson trees, random allocations and condensation

Related

• On The Joint Normality of Certain Statistics on Ordered Trees
• Optimal Algorithm for Paired-Domination in Distance-Hereditary Graphs
• Paired domination and 2- distance Paired domination of the flower graph\n f_{n\× m}
• Labelling Algorithms for Paired-domination Problems in Block and Interval Graphs
• Paired Domination versus Domination and Packing Number in Graphs