# Number of vertices that a connected dominating set can reach in densely connected graphs.

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 !

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).