# 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 !

• FWIW, the standard notation for your $> \Theta(1)$ is $\omega(1)$. Commented Nov 2, 2022 at 17:52
• So, to clarify what you are looking for, you just want any subtree $T$ that has $\Omega(n)$ neighbors that aren't in $T$? (And finding this is equivalent to finding a subtree $T'$ that has $\Omega(n)$ leaves, right? Because by removing the leaves from $T'$ you would get $T$, or, similarly, by adding the neighbors to $T$ you could get $T'$.) Commented Nov 2, 2022 at 18:18
• You are right, this is exactly what I expect. Commented Nov 3, 2022 at 1:21

Yes, there is.

Lemma 1. Let $$G$$ be any $$n$$-vertex connected graph in which $$\Omega(n)$$ vertices have degree 3 or more. Then $$G$$ contains a connected dominating set $$D$$ whose complement has size $$\Omega(n)$$.

Before we give the proof, note that this answer strengthens this result, showing that it suffices for $$G$$ to meet the following condition: the number of edges in $$G$$ such that both endpoints have degree at most two is $$O(1)$$ times the number of vertices in $$G$$ of degree three or more.

Proof of Lemma 1. Consider any spanning tree $$T$$ of $$G$$. Let $$n_1$$ and $$n_2$$ be the numbers of leaves and degree-2 vertices in $$T$$. Let $$n^+_3$$ be the number of vertices of degree three or more in $$T$$.

Let $$G_2$$ be the subgraph of $$T$$ consisting of the $$n_2$$ vertices of degree 2 in $$T$$ and the edges in $$T$$ between these vertices. (Note that $$G_2$$ is a subgraph of $$T$$, and has maximum degree 2, so is a collection of paths.) We claim that the number of edges in $$G_2$$ is at least $$n - 4n_1$$, and the number of vertices in $$G_2$$ is at least $$n-2n_1$$.

To show the claim, consider the tree $$T'$$ obtained from $$T$$ by splicing out all degree-2 vertices (that is, for each maximal path $$v_1, v_2, \ldots, v_p$$ in $$T$$ such that each intermediate vertex $$v_i$$ for $$2\le i \le p-1$$ has degree two in $$T$$, remove the path edges and the intermediate vertices, replacing them all by the edge $$(v_1, v_p)$$, which might not be in $$G$$). It is well known (and easy to show) that in $$T'$$ (as in any tree where each non-leaf node has degree 3 or more) the number of edges is at most twice the number of leaf nodes, i.e., at most $$2n_1$$. And for every edge in $$T'$$, $$G_2$$ is missing at most two edges from $$T$$, so $$G_2$$ is missing at most $$4n_1$$ edges of $$T$$. Likewise, $$T'$$ has at most $$2n_1$$ non-leaf nodes, to $$G_2$$ is missing at most $$2n_1$$ nodes of $$T$$. This shows the claim.

It follows that $$G_2$$ has at most $$4n_1$$ more nodes than edges, so consists of at most $$4n_1$$ paths (counting each isolated vertex in $$G_2$$ as a path). It follows that at least $$n-10 n_1$$ nodes in $$G_2$$ have two neighbors in $$G_2$$. That is, back in $$T$$, at least $$n-10 n_1$$ nodes in $$T$$ have the following property: they have degree 2 in $$T$$, and both of their neighbors have degree 2 in $$T$$. Call such a node typical.

Now fix $$T$$ to be a spanning tree in $$G$$ with a maximum number of leaves.

Let $$u$$ be a typical vertex in $$G$$ and consider any edge $$(u,w)$$ from $$u$$ that is not in $$T$$. Consider adding the edge $$(u, w)$$ to $$T$$, creating a cycle, and removing one of the other edges incident to $$u$$ to break the cycle (so the result is again a spanning tree). This makes one of $$u$$'s neighbors into a leaf, so by the choice of $$T$$ the vertex $$w$$ must have been a leaf in $$T$$ (otherwise the operation would increase the number of leaves). So, for every typical vertex $$u$$, each edge from $$u$$ except the two in $$T$$ goes to a leaf in $$T$$.

Assume for contradiction that $$n_1 = o(n)$$. Then there are at least $$n - 10 n_1 = n - o(n)$$ typical nodes in $$G$$, and at least $$\Omega(n)$$ nodes in $$G$$ have degree at least three. It follows that at least one of the $$n_1$$ leaves, say $$u$$, has two edges to typical vertices, say $$v_1$$ and $$v_2$$. But then by adding edges $$(u, v_1)$$ and $$(u, v_2)$$ to $$T$$, and removing one edge from $$v_1$$ and one from $$v_2$$ (thereby making a neighbor of each a leaf in the new tree), we can create a spanning tree with more leaves than $$T$$, contradicting the choice of $$T$$. So $$n_1 = \Omega(n)$$.

The non-leaf vertices of $$T$$ form a connected dominating set, whose complement (the leaves) has size $$n_1 = \Omega(n)$$. $$~~~~~\Box$$

• I have a question regarding this claim 'It follows that at least $n-8n_1$ nodes in $G_2$ have two neighbors in $G_2$'. $G_2$ only contains the $n_2$ vertices of degree $2$ in $T$, so, it should be 'at least $n_2 - 8n_1$ nodes' ? Commented Nov 3, 2022 at 11:16
• If this claim indeed contains a mistake, the proof above can only show $n_1>=n_2 /9$. However, it can be fixed and Lemma-1 is correct. By definition, we have $n_1+n_2+n_3=n-1$. So, at least one of $n_1$, $n_2$, $n_3$ is $\Theta(n)$. If it is $n_1$, then Lemma-1 is true. If it is $n_2$, since $n_1>=n_2/9$, Lemma-1 is also true. If it is $n_3$, as it is well-known that $n_1 \geq n_3+2$, we also have Lemma-1 is true. Commented Nov 3, 2022 at 11:50
• Yes, my edit introduced a gap in the proof. Namely, by the argument about $T'$, there are at least $n-2n_1$ vertices in $G_2$, that is $n_2 \ge n-2n_1$. So at least $n-2 n_1 - 8 n_1 = n - 10n_1$ nodes in $G_2$ are typical (have two neighbors in $G_2$). I'll correct the gap. Commented Nov 3, 2022 at 11:55