{"id":"arxiv/2609.29623","url":"https://arxiv.org/abs/2609.29623","tags":["math.CO"],"score":0,"title":"On Alon's problem concerning the difference between connected domination number and domination number","domain":"math.CO","source":"arxiv","authors":["Chengli Li","Bo Zhou"],"reviews":0,"subject":"math.CO","summary":"For a connected graph $G$, let $γ(G)$ and $γ_c(G)$ denote its domination number and connected domination number, respectively. Let $M(n,k)$ be the maximum of $γ_c(G)-γ(G)$ over all connected $n$-vertex graphs of minimum degree at least $k$. Alon proved that \\[ 2\\left\\lfloor\\frac{n}{k+1}\\right\\rfloor-O(1)\\le M(n,k) k+1$, let \\[ ν=\\frac{n}{k+1} \\text{ and } Φ(x)= \\frac{1}{x\\log\\!\\frac{x}{x-1}} \\ (\\text{for }x>1). \\] As $k\\to\\infty$, uniformly over all integers $n>k+1$, \\[ M(n,k)= \\big(Φ(ν)+o(1)\\big) ν\\log\\log(k+1). \\]","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-08-28","reactions":{}}