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.