Asymptotic Analysis of Domination in Random Linear Graphs via Markov Processes
Lukáš Sládek, Dušan Bernát, Pavol Bokes · 2025
We study the statistical properties of the domination number — a key measure of graph connectivity — in random linear graphs. By reformulating the problem as a Markov process and applying the Chapman–Kolmogorov equation, we compute the domination number distribution in polynomial time. As the graph grows, asymptotic methods yield a normal approximation for typical deviations via the central limit theorem and a large deviation function for tail probabilities. Moreover, explicit rational formulas for the mean and variance, expressed in terms of the edgeretention probability, are derived using computer algebra. These results establish a connection between random linear graphs and Markov processes and demonstrate the power of computer algebra in quantifying the asymptotic behavior of correlated random sums.