MMN-5033
Universal distance domination in random graphs
Gábor Bacsó; József Túri; Zsolt Tuza;Abstract
Given a graph G = (V,E), a dominating set is a subset D ⊆V such that every vertex
in V \D is adjacent with at least one vertex in D. The domination number of G, traditionally
denoted by γ(G), is the minimum cardinality of a dominating set in G.
For any natural number k, a set D is k-distance dominating—called kdd set for short—if every
vertex not in D is at distance at most d from some vertex in D. We define the universal k-distance
domination number as
uk(G) := min{d : ∀D ⊆V with |D| ≥ d,D is a kdd set in G}.
In sharp contrast to most of the standard domination parameters, determining the universal
k-distance domination number uk(G) turns out to be computable in polynomial time. We also
characterize the graphs satisfying γ(G) = u1(G), and investigate the behavior of the function uk
on random graphs.
It remains a challenging open problem to characterize the equality of k-distance domination
and universal k-distance domination numbers for a general k. A further problem is to sharpen the
estimates on the edge probability in the auxiliary graph H = Gk.
Vol. 26 (2025), No. 2, pp. 591-602