<p>Yes, there is.</p>
<p><strong>Lemma 1.</strong> <em>Let <span class="math-container">$G$</span> be any <span class="math-container">$n$</span>-vertex connected graph in which <span class="math-container">$\Omega(n)$</span> vertices have degree 3 or more.  Then <span class="math-container">$G$</span> contains a connected dominating set <span class="math-container">$D$</span> whose complement has size <span class="math-container">$\Omega(n)$</span>.</em></p>
<p>Before we give the proof, note that <a href="https://cstheory.stackexchange.com/a/52109/8237">this answer</a> strengthens this result, showing that it suffices for
<span class="math-container">$G$</span> to meet the following condition: <em>the number of edges in <span class="math-container">$G$</span> such that both endpoints have degree at most two is <span class="math-container">$O(1)$</span> times the number of vertices in <span class="math-container">$G$</span> of degree three or more.</em></p>
<p><em>Proof of Lemma 1.</em>
Consider any spanning tree <span class="math-container">$T$</span> of <span class="math-container">$G$</span>.  Let <span class="math-container">$n_1$</span> and <span class="math-container">$n_2$</span> be the numbers of leaves and degree-2 vertices in <span class="math-container">$T$</span>.  Let <span class="math-container">$n^+_3$</span> be the number of vertices of degree three or more in <span class="math-container">$T$</span>.</p>
<p>Let <span class="math-container">$G_2$</span> be the subgraph of <span class="math-container">$T$</span> consisting of the <span class="math-container">$n_2$</span> vertices of degree 2 in <span class="math-container">$T$</span> and the edges in <span class="math-container">$T$</span> between these vertices.  (Note that <span class="math-container">$G_2$</span> is a subgraph of <span class="math-container">$T$</span>, and has maximum degree 2, so is a collection of paths.)  We claim that <em>the number of edges in <span class="math-container">$G_2$</span> is at least <span class="math-container">$n - 4n_1$</span>, and the number of vertices in <span class="math-container">$G_2$</span> is at least <span class="math-container">$n-2n_1$</span>.</em></p>
<p>To show the claim, consider the tree <span class="math-container">$T'$</span> obtained from <span class="math-container">$T$</span> by splicing out all degree-2 vertices (that is, for each maximal path <span class="math-container">$v_1, v_2, \ldots, v_p$</span> in <span class="math-container">$T$</span> such that each intermediate vertex <span class="math-container">$v_i$</span> for <span class="math-container">$2\le i \le p-1$</span> has degree two in <span class="math-container">$T$</span>, remove the path edges and the intermediate vertices, replacing them all by the edge <span class="math-container">$(v_1, v_p)$</span>, which might not be in <span class="math-container">$G$</span>). It is well known (and easy to show) that in <span class="math-container">$T'$</span> (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 <span class="math-container">$2n_1$</span>.   And for every edge in <span class="math-container">$T'$</span>, <span class="math-container">$G_2$</span> is missing at most two edges from <span class="math-container">$T$</span>, so <span class="math-container">$G_2$</span> is missing at most <span class="math-container">$4n_1$</span> edges of <span class="math-container">$T$</span>. Likewise, <span class="math-container">$T'$</span> has at most <span class="math-container">$2n_1$</span> non-leaf nodes, to <span class="math-container">$G_2$</span> is missing at most <span class="math-container">$2n_1$</span> nodes of <span class="math-container">$T$</span>.  This shows the claim.</p>
<p>It follows that <span class="math-container">$G_2$</span> has at most <span class="math-container">$4n_1$</span> more nodes than edges, so consists of at most <span class="math-container">$4n_1$</span> paths (counting each isolated vertex in <span class="math-container">$G_2$</span> as a path).  It follows that at least <span class="math-container">$n-10 n_1$</span> nodes in <span class="math-container">$G_2$</span> have two neighbors in <span class="math-container">$G_2$</span>.  That is, back in <span class="math-container">$T$</span>, at least <span class="math-container">$n-10 n_1$</span> nodes in <span class="math-container">$T$</span> have the following property: they have degree 2 in <span class="math-container">$T$</span>, and both of their neighbors have degree 2 in <span class="math-container">$T$</span>.  Call such a node <em>typical</em>.</p>
<p>Now fix <span class="math-container">$T$</span> to be a spanning tree in <span class="math-container">$G$</span> with a maximum number of leaves.</p>
<p>Let <span class="math-container">$u$</span> be a typical vertex in <span class="math-container">$G$</span> and consider any edge <span class="math-container">$(u,w)$</span> from <span class="math-container">$u$</span> that is not in <span class="math-container">$T$</span>.  Consider adding the edge <span class="math-container">$(u, w)$</span>  to <span class="math-container">$T$</span>, creating a cycle, and removing one of the other edges incident to <span class="math-container">$u$</span> to break the cycle (so the result is again a spanning tree).  This makes one of <span class="math-container">$u$</span>'s neighbors into a leaf, so by the choice of <span class="math-container">$T$</span> the vertex <span class="math-container">$w$</span> must have been a leaf in <span class="math-container">$T$</span> (otherwise the operation would increase the number of leaves).  So, <em>for every typical vertex <span class="math-container">$u$</span>, each edge from <span class="math-container">$u$</span> except the two in <span class="math-container">$T$</span> goes to a leaf in <span class="math-container">$T$</span>.</em></p>
<p>Assume for contradiction that <span class="math-container">$n_1 = o(n)$</span>.
Then there are at least <span class="math-container">$n - 10 n_1 = n - o(n)$</span> typical nodes in <span class="math-container">$G$</span>, and at least <span class="math-container">$\Omega(n)$</span> nodes in <span class="math-container">$G$</span> have degree at least three.  It follows that at least one of the <span class="math-container">$n_1$</span> leaves, say <span class="math-container">$u$</span>, has two edges to typical vertices, say <span class="math-container">$v_1$</span> and <span class="math-container">$v_2$</span>.  But then by adding edges <span class="math-container">$(u, v_1)$</span> and <span class="math-container">$(u, v_2)$</span> to <span class="math-container">$T$</span>, and removing one edge from <span class="math-container">$v_1$</span> and one from <span class="math-container">$v_2$</span> (thereby making a neighbor of each a leaf in the new tree), we can create a spanning tree with more leaves than <span class="math-container">$T$</span>, contradicting the choice of <span class="math-container">$T$</span>.  So <span class="math-container">$n_1 = \Omega(n)$</span>.</p>
<p>The non-leaf vertices of <span class="math-container">$T$</span> form a connected dominating set, whose complement (the leaves) has size <span class="math-container">$n_1 = \Omega(n)$</span>. <span class="math-container">$~~~~~\Box$</span></p>

CC BY-SA 4.0
2022-11-03T11:16:04.813Z
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' ?
Mingzhou Liu
CC BY-SA 4.0
2022-11-03T11:50:04.893Z
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](https://math.stackexchange.com/questions/3990240/fewer-degree-3-nodes-than-leaf-nodes-in-a-tree) that $n_1 \geq n_3+2$, we also have Lemma-1 is true.
Mingzhou Liu
CC BY-SA 4.0
2022-11-03T11:55:48.390Z
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.
Neal Young
CC BY-SA 4.0
2022-11-02T21:32:37.830Z
2022-11-04T14:51:02.447Z
2022-11-04T14:51:02.447Z
Neal Young
<p>Consider a undirected densely connected (every vertex has <span class="math-container">$&gt;\Theta(1)$</span> incident edges) graph <span class="math-container">$G$</span>. Denote its vertices set as <span class="math-container">$\mathbf{V}$</span>, number of vertices as <span class="math-container">$n$</span>.</p>
<p>A <a href="https://en.wikipedia.org/wiki/Connected_dominating_set" rel="nofollow noreferrer">connected dominating set</a>  <span class="math-container">$\mathbf{D}\subseteq  \mathbf{V}$</span> is a subset of vertices with two properties:</p>
<ul>
<li><p>Any node in <span class="math-container">$\mathbf{D}$</span> can reach any other node in <span class="math-container">$\mathbf{D}$</span> by a path that stays entirely within <span class="math-container">$\mathbf{D}$</span>. That is, <span class="math-container">$\mathbf{D}$</span> induces a connected subgraph of <span class="math-container">$G$</span>.</p>
</li>
<li><p>Every vertex in <span class="math-container">$G$</span> either belongs to <span class="math-container">$\mathbf{D}$</span> or is adjacent to a vertex in <span class="math-container">$\mathbf{D}$</span>. That is, <span class="math-container">$\mathbf{D}$</span> is a dominating set of <span class="math-container">$G$</span>.</p>
</li>
</ul>
<p>My question is:</p>
<ul>
<li><p>In such a densely connected graph, there is always a connected dominating set <span class="math-container">$\mathbf{D}$</span> such that <span class="math-container">$|\mathbf{V}\backslash\mathbf{D}|=\Theta(n)$</span> ?</p>
</li>
<li><p>(Actually, I only expect there are <span class="math-container">$\Theta(n)$</span> vertices in <span class="math-container">$\mathbf{V}\backslash\mathbf{D}$</span> adjacent to <span class="math-container">$\mathbf{D}$</span>, it is not necessary that <span class="math-container">$\mathbf{D}$</span> is a dominating set and <em>every</em> vertex in <span class="math-container">$\mathbf{V}\backslash\mathbf{D}$</span> is adjacent to <span class="math-container">$\mathbf{D}$</span>. I do not know what's the name of such a set <span class="math-container">$\mathbf{D}$</span>, so I use connected dominating set.)</p>
</li>
</ul>
<p>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.</p>
<p>Here, <span class="math-container">$\Theta$</span> is the Big-theta notation in computational complexity. I use <span class="math-container">$&gt; \Theta(1)$</span> to denote 'larger than any constant number'.</p>
<p>Any proof or counter-example is welcomed !</p>

CC BY-SA 4.0
2022-11-02T17:52:36.630Z
FWIW, the standard notation for your $> \Theta(1)$ is $\omega(1)$.
Neal Young
CC BY-SA 4.0
2022-11-02T18:18:53.243Z
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'$.)
Neal Young
CC BY-SA 4.0
2022-11-03T01:21:10.787Z
You are right, this is exactly what I expect.
Mingzhou Liu
<graph-theory>
Number of vertices that a connected dominating set can reach in densely connected graphs
Mingzhou Liu
# Number of vertices that a connected dominating set can reach in densely connected graphs

(Asked by: username_0 on 2022-11-02)

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](https://en.wikipedia.org/wiki/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 !

**Tags:** graph-theory
> **Comments:**
> **username_1**: FWIW, the standard notation for your $> \Theta(1)$ is $\omega(1)$.  
> **username_1**: 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'$.)  
> **username_0**: You are right, this is exactly what I expect.  

---

## 1 answers

### Answer by username_1 on 2022-11-02. Score: 3 | Accepted answer

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](https://cstheory.stackexchange.com/a/52109/8237) 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$

> **Comments:**
> **username_0**: 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' ?  
> **username_0**: 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](https://math.stackexchange.com/questions/3990240/fewer-degree-3-nodes-than-leaf-nodes-in-a-tree) that $n_1 \geq n_3+2$, we also have Lemma-1 is true.  
> **username_1**: 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.  

---

