On Alon's problem concerning the difference between connected domination number and domination number
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). \]
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.29623
curl -X POST /api/v1/records/arxiv/2609.29623/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.29623/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'