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

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.

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

• Can you explain why we can assume all vertices in $G$ have degree $2$ or $3$? Jul 3 at 4:33
• @AnkitGayen Firstly, the hard instances that I used already had vertices with degrees only $2$ or $3$. Please check the paper. Secondly, for degree $1$ vertices you can attach two gadgets with it. Similar proof holds then. Jul 3 at 4:47
• Yup! two gadgets does the job. I somehow thought the same reasoning will not apply for two gadgets. Jul 3 at 5:03