<p>Yes, you can, by adapting the argument from <a href="https://cstheory.stackexchange.com/a/52100/8237">this answer</a>.
Note that in a bipartite graph <span class="math-container">$G=(A, B, E)$</span>, the set <span class="math-container">$B$</span> is a vertex cover.</p>
<p><strong>Lemma 1.</strong> <em>Let <span class="math-container">$G$</span> be any <span class="math-container">$n$</span>-vertex connected bipartite graph containing a vertex cover <span class="math-container">$B$</span> such that <span class="math-container">$\Omega(|B|)$</span> vertices in <span class="math-container">$B$</span> have degree at least three.  Then <span class="math-container">$G$</span> has a connected dominating set whose complement has size <span class="math-container">$\Omega(n)$</span>.</em></p>
<p>Before we give the proof, note that <span class="math-container">$B$</span> above exists if and only if the following holds: <em>the number of edges in <span class="math-container">$G$</span> such that both endpoints have degree at most two is <span class="math-container">$O(1)$</span> times the number of vertices in <span class="math-container">$G$</span> of degree three or more.</em></p>
<p><em>Proof of Lemma 1.</em> Let <span class="math-container">$T$</span> be a spanning tree of <span class="math-container">$G$</span> with a maximum number of leaves.  Let <span class="math-container">$n_1$</span> and <span class="math-container">$n_2$</span> be the numbers of leaves and degree-2 vertices in <span class="math-container">$T$</span>.  Let <span class="math-container">$n^+_3$</span> be the number of vertices of degree three or more in <span class="math-container">$T$</span>.  Let <span class="math-container">$n$</span> be the number of vertices in <span class="math-container">$G$</span>.</p>
<p>Let <span class="math-container">$G_2$</span> be the subgraph of <span class="math-container">$T$</span> consisting of the <span class="math-container">$n_2$</span> vertices of degree 2 in <span class="math-container">$T$</span> and the edges in <span class="math-container">$T$</span> between these vertices.  (Note that <span class="math-container">$G_2$</span> is a subgraph of <span class="math-container">$T$</span>, and has maximum degree 2, so is a collection of paths.)  As shown in <a href="https://cstheory.stackexchange.com/a/52100/8237">that answer</a>, <em>the number of edges in <span class="math-container">$G_2$</span> is at least <span class="math-container">$n - 4n_1$</span>, and the number of vertices in <span class="math-container">$G_2$</span> is at least <span class="math-container">$n-2n_1$</span>.</em></p>
<p>As <span class="math-container">$G_2$</span> has at most <span class="math-container">$n$</span> nodes and at least <span class="math-container">$n-4n_1$</span> edges, <span class="math-container">$G_2$</span> consists of at most <span class="math-container">$4 n_1$</span> paths.  Each path in <span class="math-container">$G_2$</span> contains at most one more vertex from <span class="math-container">$A$</span> than from <span class="math-container">$B$</span> (as no edge in the path has both endpoints in <span class="math-container">$A$</span>) so, letting <span class="math-container">$A$</span> be the set of vertices not in <span class="math-container">$B$</span>, we have <span class="math-container">$|B\cap G_2| \ge |A\cap G_2| - 4n_1$</span>.</p>
<p>As <span class="math-container">$|B\cap G_2| + |A\cap G_2| = |G_2| \ge n-2n_1$</span>, it follows that <span class="math-container">$2|B\cap G_2| \ge n - 6n_1$</span>, which implies <span class="math-container">$|B| \ge n/2 - 3n_1$</span>.</p>
<p>The non-leaf vertices of <span class="math-container">$T$</span> form a connected dominating set, whose complement (the leaves) has size <span class="math-container">$n_1$</span>.  So if <span class="math-container">$n_1 \ge n/9$</span> we are done.</p>
<p>In the remaining case we have <span class="math-container">$|B| \ge n/2 - 3n/9 = \Omega(n)$</span>, so <span class="math-container">$G$</span> has <span class="math-container">$\Omega(n)$</span> vertices of degree three or more, and by Lemma 1 in <a href="https://cstheory.stackexchange.com/a/52100/8237">the previous answer</a>, <span class="math-container">$G$</span> has a connected dominating set whose complement has size <span class="math-container">$\Omega(n)$</span>. <span class="math-container">$~~~\Box$</span></p>

CC BY-SA 4.0
2022-11-03T02:14:22.987Z
2022-11-04T14:37:17.977Z
2022-11-04T14:37:17.977Z
Neal Young
<p>Let <span class="math-container">$G$</span> a <a href="https://en.wikipedia.org/wiki/Bipartite_graph" rel="nofollow noreferrer">bipartite graph</a> with two disjoint set of vertices <span class="math-container">$\mathbf{A}$</span> and <span class="math-container">$\mathbf{B}$</span>.</p>
<p>Denote <span class="math-container">$n_a:=|\mathbf{A}|$</span>, <span class="math-container">$n_b:=|\mathbf{B}|$</span>. Suppose the following conditions hold:</p>
<ul>
<li><p><span class="math-container">$\Theta(1)&lt;n_b&lt;\Theta(n_a)$</span>.</p>
</li>
<li><p><span class="math-container">$\Theta(1)&lt;\min\mathrm{deg}(\mathbf{B})&lt;\max\mathrm{deg}(\mathbf{B})&lt;\Theta(n_a)$</span>.</p>
</li>
<li><p>The set <span class="math-container">$\mathbf{B}$</span> is a dominating set, i.e., any vertex <span class="math-container">$A_i \in \mathbf{A}$</span> is connected to <span class="math-container">$\mathbf{B}$</span>.</p>
</li>
<li><p>There are <span class="math-container">$\Theta(n_a)$</span> vertices in <span class="math-container">$\mathbf{A}$</span> that are connected to at least <span class="math-container">$2$</span> vertices in <span class="math-container">$\mathbf{B}$</span>.</p>
</li>
</ul>
<p>My question is:</p>
<ul>
<li>Can we construct a <a href="https://en.wikipedia.org/wiki/Connected_dominating_set" rel="nofollow noreferrer">connected dominating set</a> <span class="math-container">$\mathbf{D}$</span> such that <span class="math-container">$|(\mathbf{A}\cup \mathbf{B}) \backslash \mathbf{D}| = \Theta(n_a)$</span> ?</li>
</ul>
<p>Here, <span class="math-container">$\Theta$</span> is the <a href="https://stackoverflow.com/questions/10376740/what-exactly-does-big-%D3%A8-notation-represent">Big-theta notation</a> in computational complexity.</p>
<p>Any proof, counter-example, or proof ideas are welcomed.</p>

CC BY-SA 4.0
2022-11-03T01:44:27.903Z
Yes, you can assume the given graph is a connected one.
Mingzhou Liu
CC BY-SA 4.0
2022-11-03T01:51:25.163Z
I mean $(\mathbf{A} \cup \mathbf{B})\backslash \mathbf{D}$, i.e., the component set of $\mathbf{D}$.
Mingzhou Liu
CC BY-SA 4.0
2022-11-03T01:52:40.530Z
Yes, as stated, we can assume min deg of $\mathbf{B}$ is larger than any constant number.
Mingzhou Liu
CC BY-SA 4.0
2022-11-03T01:58:17.360Z
Yes, that is correct.
Mingzhou Liu
<graph-theory><bipartite-graphs><spanning-tree>
Connected dominating set in bipartite graphs
Mingzhou Liu
# Connected dominating set in bipartite graphs

(Asked by: username_0 on 2022-11-03)

Let $G$ a [bipartite graph](https://en.wikipedia.org/wiki/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](https://en.wikipedia.org/wiki/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](https://stackoverflow.com/questions/10376740/what-exactly-does-big-%D3%A8-notation-represent) in computational complexity.

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

**Tags:** graph-theory, bipartite-graphs, spanning-tree

> **Comments:**
> **username_0**: Yes, you can assume the given graph is a connected one.  
> **username_0**: I mean $(\mathbf{A} \cup \mathbf{B})\backslash \mathbf{D}$, i.e., the component set of $\mathbf{D}$.  
> **username_0**: Yes, as stated, we can assume min deg of $\mathbf{B}$ is larger than any constant number.  
> **username_0**: Yes, that is correct.  

---

## 1 answers

### Answer by username_1 on 2022-11-03. Score: 4 | Accepted answer

Yes, you can, by adapting the argument from [this answer](https://cstheory.stackexchange.com/a/52100/8237).
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](https://cstheory.stackexchange.com/a/52100/8237), *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](https://cstheory.stackexchange.com/a/52100/8237), $G$ has a connected dominating set whose complement has size $\Omega(n)$. $~~~\Box$


---

