Let $G$ a bipartite graph with two disjoint set of vertices $\mathbf{A}$ and $\mathbf{B}$.

Denote $n_a:=|\mathbf{A}|$, $n_b:=|\mathbf{B}|$. Suppose the following conditions hold:

  • $\Theta(1)<n_b<\Theta(n_a)$.

  • $\Theta(1)<\min\mathrm{deg}(\mathbf{B})<\max\mathrm{deg}(\mathbf{B})<\Theta(n_a)$.

  • The set $\mathbf{B}$ is a dominating set, i.e., any vertex $A_i \in \mathbf{A}$ is connected to $\mathbf{B}$.

  • There are $\Theta(n_a)$ vertices in $\mathbf{A}$ that are connected to at least $2$ vertices in $\mathbf{B}$.

My question is:

  • Can we construct a connected dominating set $\mathbf{D}$ such that $|(\mathbf{A}\cup \mathbf{B}) \backslash \mathbf{D}| = \Theta(n_a)$ ?

Here, $\Theta$ is the Big-theta notation in computational complexity.

Any proof, counter-example, or proof ideas are welcomed.

  • $\begingroup$ Yes, you can assume the given graph is a connected one. $\endgroup$ Nov 3, 2022 at 1:44
  • $\begingroup$ I mean $(\mathbf{A} \cup \mathbf{B})\backslash \mathbf{D}$, i.e., the component set of $\mathbf{D}$. $\endgroup$ Nov 3, 2022 at 1:51
  • $\begingroup$ Yes, as stated, we can assume min deg of $\mathbf{B}$ is larger than any constant number. $\endgroup$ Nov 3, 2022 at 1:52
  • $\begingroup$ Yes, that is correct. $\endgroup$ Nov 3, 2022 at 1:58

1 Answer 1


Yes, you can, by adapting the argument from this answer. Note that in a bipartite graph $G=(A, B, E)$, the set $B$ is a vertex cover.

Lemma 1. Let $G$ be any $n$-vertex connected bipartite graph containing a vertex cover $B$ such that $\Omega(|B|)$ vertices in $B$ have degree at least three. Then $G$ has a connected dominating set whose complement has size $\Omega(n)$.

Before we give the proof, note that $B$ above exists if and only if the following holds: 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. Let $T$ be a spanning tree of $G$ with a maximum number of leaves. 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 $n$ be the number of vertices in $G$.

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.) As shown in that answer, 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$.

As $G_2$ has at most $n$ nodes and at least $n-4n_1$ edges, $G_2$ consists of at most $4 n_1$ paths. Each path in $G_2$ contains at most one more vertex from $A$ than from $B$ (as no edge in the path has both endpoints in $A$) so, letting $A$ be the set of vertices not in $B$, we have $|B\cap G_2| \ge |A\cap G_2| - 4n_1$.

As $|B\cap G_2| + |A\cap G_2| = |G_2| \ge n-2n_1$, it follows that $2|B\cap G_2| \ge n - 6n_1$, which implies $|B| \ge n/2 - 3n_1$.

The non-leaf vertices of $T$ form a connected dominating set, whose complement (the leaves) has size $n_1$. So if $n_1 \ge n/9$ we are done.

In the remaining case we have $|B| \ge n/2 - 3n/9 = \Omega(n)$, so $G$ has $\Omega(n)$ vertices of degree three or more, and by Lemma 1 in the previous answer, $G$ has a connected dominating set whose complement has size $\Omega(n)$. $~~~\Box$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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