Consider a undirected densely connected (every vertex has $>\Theta(1)$ incident edges) graph $G$. Denote its vertices set as $\mathbf{V}$, number of vertices as $n$.

A connected dominating set $\mathbf{D}\subseteq \mathbf{V}$ is a subset of vertices with two properties:

  • Any node in $\mathbf{D}$ can reach any other node in $\mathbf{D}$ by a path that stays entirely within $\mathbf{D}$. That is, $\mathbf{D}$ induces a connected subgraph of $G$.

  • Every vertex in $G$ either belongs to $\mathbf{D}$ or is adjacent to a vertex in $\mathbf{D}$. That is, $\mathbf{D}$ is a dominating set of $G$.

My question is:

  • In such a densely connected graph, there is always a connected dominating set $\mathbf{D}$ such that $|\mathbf{V}\backslash\mathbf{D}|=\Theta(n)$ ?

  • (Actually, I only expect there are $\Theta(n)$ vertices in $\mathbf{V}\backslash\mathbf{D}$ adjacent to $\mathbf{D}$, it is not necessary that $\mathbf{D}$ is a dominating set and every vertex in $\mathbf{V}\backslash\mathbf{D}$ is adjacent to $\mathbf{D}$. I do not know what's the name of such a set $\mathbf{D}$, so I use connected dominating set.)

I am aware of that it is NP-complete to test whether there exists a connected dominating set with size less than a given threshold. But I am not sure whether it is still hard in my setting.

Here, $\Theta$ is the Big-theta notation in computational complexity. I use $> \Theta(1)$ to denote 'larger than any constant number'.

Any proof or counter-example is welcomed !


1 Answer 1


Look at this paper: https://faculty.math.illinois.edu/~west/pubs/manyleaf.pdf For large $k$, they prove that any connected graph with minimum degree $k$ has a spanning tree with linearly many leaves (actually $n(1 - O(\ln k / k))$ many leaves).

If you remove the leaves from any spanning tree, what is left is a connected dominating set. So that's a proof!


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .