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
    $\begingroup$ FWIW, the standard notation for your $> \Theta(1)$ is $\omega(1)$. $\endgroup$
    – Neal Young
    Commented Nov 2, 2022 at 17:52
  • $\begingroup$ 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'$.) $\endgroup$
    – Neal Young
    Commented Nov 2, 2022 at 18:18
  • $\begingroup$ You are right, this is exactly what I expect. $\endgroup$ Commented Nov 3, 2022 at 1:21

1 Answer 1


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$

  • $\begingroup$ 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' ? $\endgroup$ Commented Nov 3, 2022 at 11:16
  • $\begingroup$ 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. $\endgroup$ Commented Nov 3, 2022 at 11:50
  • $\begingroup$ 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. $\endgroup$
    – Neal Young
    Commented Nov 3, 2022 at 11:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.