# Connected dominating set in bipartite graphs

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).

• $$\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.

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

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$$