On hardness of finding dominating sets in triangle-free regular graphs

Question

A $k$-regular graph is one in which every vertex has degree k. A triangle-free graph is one in which any three vertices do not form a triangle. A dominating set $D$ of a graph $G$ is a set of vertices such that $\forall v \in (V(G)\setminus D)$, $v$ has a neighbour in $D$.

Is anything known about the hardness of deciding whether there is a dominating set of a given size in $k$-regular triangle-free graphs?($k\geq3$). It is already known that this problem is $NP-complete$ for triangle-free graphs.

Answer 1

We show that the minimum dominating set (MDS) problem is $\mathsf{NP}$-hard on $3$-regular triangle-free graphs. We show this by a reduction from the bipartite graphs of maximum degree $3$.

The MDS problem is $\mathsf{NP}$-hard on the bipartite graphs with maximum degree $3$ as shown in Theorem 6 of this paper. The reduction would imply that the problem is $\mathsf{NP}$-hard on $3$-regular triangle-free as well.

The following is the reduction:

Let $G$ be any bipartite graphs of maximum degree $3$. Note that $G$ is already triangle-free since it is bipartite. Moreover, we can assume that all the vertices in $G$ have degree either $2$ or $3$. Now, we create a $3$-regular triangle-free $G'$ as follows. For every vertex $v \in G$ of degree two, we define a gadget $G_{cv}$ shown below:

We connect vertex $v$ to gadget $G_{cv}$ with edge $(v,v_a)$. Let the new graph be $G'$. Note that $G'$ is $3$-regular triangle-free graph by construction. Now, the following claim easily follows:

Claim: $G$ has a dominating set of size $k$ if and only if $G'$ has a dominating set of size $k+2|V_t|$, where $|V_t|$ are the number of vertices in $G$ with degree two.

Proof: ($\to$) Suppose $G$ has a dominating set of size $k$. For every gadget $G_{cv}$, we add the vertices $v_b$ and $v_c$ to the dominating set. The vertices $v_b$ and $v_c$ dominates all the vertices in a gadget. Thus, $G'$ has a dominating set of size $k + 2|V_t|$.

($\gets$) Suppose $G'$ has a dominating set of size $k + 2|V_t|$. It is easy to see that to dominate all vertices in a gadget, we require at least two vertices. Moreover, if $v_a$ is included in the dominating set then we still require two more vertices to dominate all the vertices in a gadget. Therefore, if any gadget has vertex $v_a$ included in the dominating set, we can replace vertex $v_a$ with $v$ in the dominating set. Moreover, the other vertices of the gadget chosen in the dominating set, we replace them with $v_b$ and $v_c$. Thus, $G'$ has a dominating set of size at most $k + 2|V_t|$ such that it does not include any vertex $v_a$ and each gadget contains exactly two vertices. Thus, the vertices in the dominating set that comes from $G$ have size at most $k$ and they dominate all the vertices of $G$. Thus, $G$ has a dominating set of size $k$.