Connected dominating set in bipartite graphs

Question

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.

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$