# Some New Results on Efficient and Perfect Edge Domination of Graphs

Vinicius L. do Forte
Universidade Federal Rural do Rio de Janeiro
Rio de Janeiro Brazil
<EMAIL_ADDRESS>
Min Chih Lin
Instituto de Cálculo and Departamento de Computación
Universidad de Buenos Aires
Buenos Aires, Argentina
<EMAIL_ADDRESS>
Abilio Lucena
Programa de Engenharia de Sistemas e Computação
Universidade Federal do Rio de Janeiro
Rio de Janeiro, Brazil
<EMAIL_ADDRESS>
Nelson Maculan
Programa de Engenharia de Sistemas e Computação
Universidade Federal do Rio de Janeiro
Rio de Janeiro, Brazil
<EMAIL_ADDRESS>
Veronica A. Moyano
Instituto de Ciencias
Universidad Nacional de General Sarmiento
Buenos Aires, Argentina
<EMAIL_ADDRESS>
Jayme L. Szwarcfiter
Programa de Engenharia de Sistemas e Computação
Universidade Federal do Rio de Janeiro
Rio de Janeiro, Brazil
Instituto de Matemática e Estatística
Universidade do Estado do Rio de Janeiro
Rio de Janeiro, Brazil

###### Abstract

A neighborhood star-free graph is one in which every vertex of degree at least
two is contained in a triangle. This class has been considered before, in the
context of edge domination. In the present paper, we study the complexity of
the dominating induced matching problem for the class, and prove that the
corresponding decision problem is NP-complete for several subclasses of
neighborhood star-free graphs. In addition, we show that the dominating
induced matching problem can be solved in polynomial time for neighborhood
star-free graphs, containing no crickets as induced subgraphs.

keyword:  Neighborhood-star-free graphs Triangl Efficient edge domination
Perfect edge domination Dominating induced matching CricketsCubic planar
monotone 1in3SAT Planar $C_{4}$-free positive 1in3SAT

##  1 Introduction

A graph with vertex set $V$ and edge set $E$ is denoted by $G=(V,E)$, and the
number of vertices and edges is $|V|=n$ and $|E|=m$, respectively. The open
and closed neighborhoods of $v\in V$ are denoted by $N(v)$ and $N[v]$,
respectively. Write $d(v)$ for the degree of $v$. For $V^{\prime}\subseteq V$,
$G[V^{\prime}]$ represents the subgraph of $G$ induced by $V^{\prime}$. A
_star_ is the bipartite graph $K_{1,t}$, for some $t\geq 1$.

We say that $G=(V,E)$ is neighborhood-star-free graph, NSF graph for short, if
for every vertex $v\in V$ with degree at least 2, $G[N[v]]$, is not a _star_.
In other words, every vertex $v\in V$ is contained in some triangle, for
$d(v)\geq 2$. Such a class of graphs seems natural, in some different ways.
For instance, to model human relationships, as the common case where every
individual is acquainted with at least a pair of individuals, which are
themselves acquainted. In this paper, we explore the use of this class in the
problems of perfect and efficient edge domination of graphs. We remark that
neighborhood-star-free graphs are not necessarily closed under induced
subgraphs.

For a graph $G=(V,E)$, every edge $e\in E$ _dominates_ itself and all edges
adjacent to $e$. A subset $E^{\prime}\subseteq E$ is an _edge dominator_ of
$G$, if $E^{\prime}$ dominates every edge $e\in E$ of $G$. In particular, if
each edge $e\in E$ is dominated exactly by one edge then $E^{\prime}$ is
called an _efficient edge dominating set (EED)_. On the other hand, if we
relax the definition, and let each of $e\in E\setminus E^{\prime}$ be
dominated exactly by one edge then $E^{\prime}$ is called an _perfect edge
dominating set (PED)_. It follows from the definitions that every EED is also
a PED. Observe that a graph does not necessarily contain an EED. However,
every graph always contains a PED. In particular, the entire edge set $E$ is
always a PED, called _trivial_. Every PED which is not trivial and not an EED
is called _proper_.

In [16], the authors proved that neighborhood-star-free graphs do not have any
proper perfect dominating set. The only possible PEDs of these graphs are (i)
the trivial PED, and (ii) EEDs.

In this article, we show that deciding if a neighborhood-star-free graph
contains an EED is an NP-Complete problem. In fact, we describe NP-
Completeness proofs for several subclasses of neighborhood-star-free graphs.
In addition, we give a polynomial-time algorithm to solve the EED problem for
neighborhood-star-free which are cricket-free graphs, using a reduction
motivated by that for claw-free graphs in [11, 18].

We briefly describe some known results related to the present paper.

There is a concept of bi-coloring associated to an EED set [11] as follows.
Given a graph $G=(V,E)$ and an EED $E^{\prime}\subseteq E$ of $G$, vertices of
$G$ can be classified into two color classes.

black vertices

if they have exactly one incident edge of $E^{\prime}$. We denote this subset
of vertices by $B$.

white vertices

if they do not have any incident edge of $E^{\prime}$. We denote this subset
of vertices by $W$.

We call $(B,W)$ the _bi-coloring associated_ to $E^{\prime}$.

######  Observation 1.

The subset $B$ of $G$ induces in $G$ the EED $E^{\prime}$. Moreover
$E^{\prime}$ is an induced matching of $G$.

For the above reason, an EED is also called _dominating induced matching
(DIM)_ of $G$. From now on, we will use either the terms EED or DIM, with the
same meaning.

The following rules are useful to verify if a bi-coloring of a graph $G$ is
associated to some DIM of $G$. In the positive case, we say that it is a
_valid_ bi-coloring of $G$.

######  Theorem 1.

[11] Given a graph $G$ and a bi-coloring $(B,W)$ of $G$. Then $(B,W)$ is valid
if and only if it verifies the following conditions.

  * •

$G[B]$ is 1-regular which means every black vertex has exactly one black
neighbor.

  * •

$W$ is an independent set. That is, all neighbors of white vertices have black
color.

As in [17], assigning one of the two possible colors to vertices of $G$ is
called a _coloring_ of $G$. A coloring is _partial_ if only part of the
vertices of $G$ have been assigned colors, otherwise is _total_.

######  Definition 1.

[17] A partial coloring of $G$ is _valid_ if verifies the following
conditions.

  * •

White vertices is an independent set.

  * •

Every black vertex has at most one black neighbor.

  * •

Every black vertex without black neighbors has an uncolored neighbor.

It is clear that any invalid partial coloring cannot be extended to a valid
total coloring.

(a) $k$-star=$K_{1,k}$(b) $2$-star$=K_{1,2}$(c) $3$-star=$K_{1,3}$=claw(d)
cricket

(e) butterfly(f) paw(g) diamond(h) gem

(i) $H=H_{1}$(j) $H_{2}$(k) snail(m) press

Figure 1: Some graphs of interests (a) $K_{4}=W_{3}$(b) $W_{4}$(c) $W_{5}$
Figure 2: Some wheels

For the next definitions, we need some more basic terminology.

A vertex is _universal_ if it is neighbor of all other vertices of the graph.
A vertex is _simplicial_ if the subgraph induced by its neighborhood is
complete. Next we define some of the graphs depicted in Figure 1. A
_butterfly_ is a neighborhood-star-free graph that consists of exactly two
triangles sharing a single vertex. We call this vertex its _central_ vertex.
If we remove any vertex except the central vertex, the resulting graph is a
_paw_. A _pendant_ or _leaf_ vertex is a vertex of degree one and its unique
neighbor is a _preleaf_ vertex. $P_{k}$ is a connected graph with exactly
$k-2$ vertices of degree 2 and two leaves. $C_{k}$ is a connected graph of $k$
vertices of degree 2. A _wheel_ $W_{k}$ is a $C_{k}$ plus a universal vertex
(see Figure 2). A _diamond_ is the resulting graph after deleting an edge from
a $K_{4}$. A _gem_ is a $P_{4}$ plus a universal vertex. An $H$ graph is two
copies of $P_{3}$ plus an edge connecting both middle vertices of $P_{3}$’s.
The latter edge is the _middle_ edge of $H$. $H_{k}$ is replacing the middle
edge $(v,u)$ of $H$ by a path $P_{k+1}$ that connects $v$ and $u$. Exactly
$k-1$ new vertices of degree 2 are added. A _snail_ is obtained by adding 3
pendant vertices to a triangle, in such a way that two of them become adjacent
to the same vertex of the triangle. A _press_ graph consists of two copies of
paw plus an edge connecting a degree 2 vertex of each paw.

There are some structures and properties related to valid bi-colorings.

######  Theorem 2.

[11] Given a graph $G$ and any valid bi-coloring $(B,W)$ of $G$

  * •

Any triangle of $G$ has exactly one white vertex.

  * •

The central vertex of an induced butterfly $F$ of $G$ is the unique white
vertex of $F$.

  * •

The odd degree vertices in an induced paw of $G$ have different colors.

  * •

In an induced diamond, the vertices of degree 2 are white and the other two
vertices are black.

In [11, 18], the authors proposed algorithms to solve the DIM problem on claw-
free graphs. In order to obtain a valid total coloring that represents a
solution of DIM, they first pre-color some vertices of the graph by applying a
set of rules and if this coloring is not total (meaning that some vertices are
still uncolored) but feasible to be extended to a total valid coloring. In
this case, they assure that any triangle has (i) zero, (ii) two, or (iii)
three uncolored vertices (in case (ii), the only colored vertex must be black
and it has no black-colored neighbor) and any uncolored vertex must meet one
of the following conditions:

(a) it has degree 2 with two adjacent neighbors, or

(b) it has degree 3 and exactly two of its three neighbors are adjacent.

Finally, they consider the residual graph $G_{0}$ after deleting those colored
vertices that have no neighbors among uncolored ones.

######  Lemma 1.

[11] $G_{0}$ admits a total valid coloring.

With this lemma, automatically, we get a total valid coloring for the original
graph. This extension can be done in $O(n)$ time [18], where $n$ is the number
of vertices of $G$.

There is a vast literature on dominating induced matchings. It includes [11,
1, 3, 4, 2, 5, 6, 7, 13, 14, 15, 23, 15, 8, 9, 10, 20]. Papers on perfect edge
domination are less frequent. The reader can refer to [16, 22, 19, 12]. In the
latter paper, the authors describe ILP formulations for the PED problem,
together with some experimental results.

##  2 NP-Completeness results

We consider in this work two variants of the 1in3SAT problem, one of them is a
well-known NP-Complete problem, and we prove that the other one is NP-
Complete. Then, we reduce them to the existence of DIMs on some subclasses of
neighborhood-star-free graphs.

Given a formula $F$ in conjunctive normal form (CNF), its associated graph
$G(F)$ is a bipartite graph where one of the classes of the bipartition
corresponds to the clauses and the other one to the variables. We follow the
convention of previous articles in this field, using rectangles to represent
vertices corresponding to clauses and circles for those that are associated to
variables. In $G(F)$, two vertices are neighbors if one of them corresponds to
a variable $x_{j}$ (circle), the other one corresponds to a clause $C_{i}$
(rectangle), and $x_{j}$ or $\neg x_{j}$ is a literal of $C_{i}$. As we work
with 1in3SAT, every clause of $F$ has exactly three different literals which
implies that every clause (rectangle) vertex has degree 3 in $G(F)$. We say
that an assignment is _valid_ if in every clause there is exactly one true
literal. Two formulas $F$ and $F^{\prime}$ in CNF are equivalent if there is a
valid assignment for $F$ if only if there is a valid assignment for
$F^{\prime}$. A formula $F$ is _monotone_ if all literals in $F$ are positive
or all literals in $F$ are negative. In case that all literals are positive
(negative) then $F$ is positive (negative). We define that a formula $F$ is
_variable-monotone_ if, for every variable, its literals are all positive, or
they are all negative. Clearly, monotone formulas are variable-monotone. Given
a variable-monotone formula $F$,  define a new positive formula $F^{\prime}$
as follows. For each variable of $F$ whose literals are (all) negative,
replace such literals with their complements. It is clear that the formula
$F^{\prime}$ is positive. It is not hard to see that $F$ is equivalent to
$F^{\prime}$ and their associated graphs are identical. We call $F^{\prime}$
the _positivized_ formula of $F$. Therefore, instead of asking if there is a
valid assignment for $F$, we can ask for its positivized formula $F^{\prime}$.

On the other hand, it is highly probable that the associated graphs of hard
instances (to determine if there is a valid assignment) contain some induced
$C_{4}$. In many NP-completeness proofs variants of 1in3SAT (for instance
[21]), the reduction adds two clauses that repeat two literals in order to
assure that the third literal has the same value in any valid assignment. This
action makes the associated graph to contain induced $C_{4}$’s.

Below are the three decision problems that we deal with in this article.

Firstly, the known NP-Complete variant of 1in3SAT and its NP-Completeness
proof can be found in [21].

CUBIC PLANAR MONOTONE 1in3SAT
INPUT: A monotone formula $F$ in CNF, each clause is a disjunction of exactly
three different literals and the associated graph $G(F)$ is planar cubic
QUESTION: Is there a valid assignment for $F$?

Secondly, the new proposed variant of 1in3SAT.

SUBCUBIC PLANAR $C_{4}$-FREE positive 1in3SAT
INPUT: A positive formula $F$ in CNF, each clause is a disjunction of exactly
three different literals and the associated graph $G(F)$ is planar,
$C_{4}$-free, with degree at most 3
QUESTION: Is there a valid assignment for $F$?

Finally, our target problem.

EXISTENCE OF DIM
INPUT: Graph $G$
QUESTION: Does $G$ contain a dominating induced matching?

Next we prove that the variant of 1in3SAT proposed is NP-complete.

######  Theorem 3.

Planar subcubic $C_{4}$-free positive 1in3SAT is NP-Complete.

###### Proof.

Firstly we describe a polynomial-time reduction from an input instance of
Cubic planar monotone 1in3SAT, a formula $F$, to an input instance of Subcubic
planar $C_{4}$-free positive 1in3SAT, a formula $F^{\prime\prime}$. Secondly,
we show that $F$ and $F^{\prime\prime}$ are equivalent. This will prove that
planar subcubic $C_{4}$-free positive 1in3SAT is NP-Complete.

The reduction will consider the equivalent positivized formula $F^{\prime}$ of
$F$ as input (where all literals are positive). The associated graph
$G(F^{\prime})=G(F)$ is planar cubic bipartite. Every variable $y_{i}$ of
$F^{\prime}$, appears exactly in 3 clauses $C_{i}^{1},C_{i}^{2},C_{i}^{3}$ as
positive literal. We replace $y_{i}$ by three variables
$x_{i}^{1},x_{i}^{2},x_{i}^{3}$ and $x_{i}^{j}$ replaces $y_{i}$ as positive
literal in $C_{i}^{j}$ for $j=1,2,3$. In order to assure that
$x_{i}^{1},x_{i}^{2},x_{i}^{3}$ have the same value in every valid assignment,
we add 8 new clauses and 10 additional variables as follows (see Figure 3):

For $j=1,2$

$\qquad\qquad x_{i}^{j}\vee w_{i,j}^{1}\vee w_{i,j}^{2}$

$\qquad\qquad w_{i,j}^{1}\vee w_{i,j}^{3}\vee w_{i,j}^{4}$

$\qquad\qquad x_{i}^{j+1}\vee w_{i,j}^{4}\vee w_{i,j}^{5}$

$\qquad\qquad w_{i,j}^{2}\vee w_{i,j}^{3}\vee w_{i,j}^{5}$

$y_{i}$$C^{2}_{i}$$C^{1}_{i}$$C^{3}_{i}$ | $C^{2}_{i}$$C^{1}_{i}$$C^{3}_{i}$$x^{2}_{i}$$w^{4}_{i,1}$$w^{5}_{i,1}$$w^{3}_{i,1}$$w^{1}_{i,1}$$w^{2}_{i,1}$$x^{1}_{i}$$w^{2}_{i,2}$$w^{1}_{i,2}$$w^{3}_{i,2}$$w^{5}_{i,2}$$w^{4}_{i,2}$$x^{3}_{i}$
---|---
Figure 3: Reduction employed in the NP completeness proof

We show that $w_{i,j}^{1},w_{i,j}^{5}$ have the same value in any valid
assignment. If $w_{i,j}^{1}$ is true, then
$x_{i}^{j},w_{i,j}^{2},w_{i,j}^{3},w_{i,j}^{4}$ should be false. Therefore,
$w_{i,j}^{5}$ should be the true literal in $w_{i,j}^{2}\vee w_{i,j}^{3}\vee
w_{i,j}^{5}$. Symmetrically, if $w_{i,j}^{5}$ is true, then
$x_{i}^{j+1},w_{i,j}^{2},w_{i,j}^{3},w_{i,j}^{4}$ should be false. Therefore,
$w_{i,j}^{1}$ should be the true literal in $w_{i,j}^{3}\vee w_{i,j}^{4}\vee
w_{i,j}^{5}$. Now, we prove that $x_{i}^{j},x_{i}^{j+1}$ have the same value
in any valid assignment. In case that $w_{i,j}^{1},w_{i,j}^{5}$ are true, then
$x_{i}^{j},x_{i}^{j+1}$ are both false. Then, we can assume that
$w_{i,j}^{1},w_{i,j}^{5}$ are false. If $x_{i}^{j}$ is true, then
$w_{i,j}^{2}$ is false and $w_{i,j}^{3}$ should be the true literal in
$w_{i,j}^{2}\vee w_{i,j}^{3}\vee w_{i,j}^{5}$. Consequently, $w_{i,j}^{4}$ is
false and $x_{i}^{j+1}$ should be the true literal in $x_{i}^{j+1}\vee
w_{i,j}^{4}\vee w_{i,j}^{5}$. Symmetrically, if $x_{i}^{j+1}$ is true,
$x_{i}^{j}$ would be true using a similar deduction. As a consequence,
$x_{i}^{1},x_{i}^{2},x_{i}^{3}$ have the same value in every valid assignment
as we need. Note that all these variables except $x_{i}^{1},x_{i}^{3}$ are
literals of exactly 2 of these 8 clauses. $x_{i}^{1},x_{i}^{3}$ appear only
once. But solely, $x_{i}^{1},x_{i}^{2},x_{i}^{3}$ appear in exactly one other
clause ($C_{i}^{1},C_{i}^{2},C_{i}^{3}$, respectively). In conclusion, every
variable appears at most in 3 clauses. Clearly, the resulting formula
$F^{\prime\prime}$ is equivalent to $F^{\prime}$ and $F$. If $F^{\prime}$
($F$) uses $n$ variables and $m$ clauses, then $F^{\prime\prime}$ has exactly
$13n$ variables and $m+8n$ clauses. Therefore, $F^{\prime\prime}$ can be
obtained in polynomial time. As all clauses have exactly 3 literals, the
associated graph $G(F^{\prime\prime})$ has maximum degree 3. In case that
$G(F^{\prime\prime})$ has an induced $C_{4}$ (see Figure 4). Two of the
vertices of this $C_{4}$ correspond to clauses and the other two variables
meaning that those two clauses have both variables as literals. This situation
does not occur in the formula $F^{\prime\prime}$. The original $m$ clauses
have their local copies of variables. They do not have any variable in common.
Any pair of the new $8n$ clauses have at most one variable in common. An
original clause and a new one can have at most one variable $x_{i}^{j}$ in
common. Therefore, $G(F^{\prime\prime})$ is $C_{4}$-free. Given a planar
representation of $G(F^{\prime})=G(F)$, this representation can be easily
transformed to a planar representation of $G(F^{\prime\prime})$ (see Figure
3). Finally, we can conclude that $G(F^{\prime\prime})$ is planar subcubic
$C_{4}$-free. Consequently, we can state that subcubic planar $C_{4}$-free
positive 1in3SAT is NP-Complete. ∎

$C_{1}$$C_{2}$$X_{i}$$X_{j}$ Figure 4: An induced $C_{4}$ cannot exist in the
associated graph $G(F^{\prime\prime})$

Now, we give a polynomial-time reduction from an instance of input of Subcubic
Planar $C_{4}$-free positive 1in3SAT, a positive formula $F$ in CNF, to a
graph $S(G(F))$ an instance of our final target problem.

Given such positive formula $F$ where each clause is a disjunction of exactly
three different literals and its associate graph $G(F)$ is planar $C_{4}$-free
with degree at most 3, we construct a graph $S(G(F))$ from $G(F)$ as follows.

  1. 1.

Replace every rectangle vertex $v$ (corresponding to a clause $C_{i}$) of
$G(F)$ by a triangle (clause triangle). Each vertex of this triangle takes a
different neighbor (a circle vertex corresponding to a variable) of $v$ as its
owner (see Figure 5). Call this resulting graph as _temporary_ graph
$T(G(F))$.

  2. 2.

For each circle vertex $w$, add two mutually adjacent new vertices as its
neighbors forming a triangle (vertex triangle) (see Figure 6). This final
graph is the graph $S(G(F))$.

For our convenience, we call this construction as Main Transformation.

Clearly, $S(G(F))$ can be obtained in polynomial-time from $F$. If $F$ has $n$
variables and $m$ clauses, then $S(G(F))$ has exactly $3n+3m$ vertices and
$3n+6m$ edges.

######  Theorem 4.

$S(G(F))$ is planar neighborhood-star-free ($K_{4}$,diamond,butterfly,
$K_{1,5}$,$H$,snail,press,$C_{4}$,$C_{5}$,$C_{6}$,$C_{7}$,$C_{8}$,$C_{3t+1}$,$C_{3t+2}$)-free
for $t\geq 3$ without pendant vertices.

###### Proof.

Every vertex of $S(G(F))$ is in exactly one triangle which implies that
$S(G(F))$ is neighborhood-star-free without pendant vertices and ($K_{4}$,
diamond, butterfly)-free.

Every vertex $u$ of a clause triangle $T$ has exactly one neighbor $z\not\in
T$ and $z$ is in a vertex triangle ($u$ has degree 3). Every vertex triangle
has exactly two simplicial vertices and both of degree two. It is clear that
the only vertices that can have degree more than 3 in $S(G(F))$ are those
corresponding to circle vertices in $G(F)$. They have degree at most 3 in
$G(F)$ but in $S(G(F))$, they have two additional neighbors. Hence, they have
degree at most 5 in $S(G(F))$. As every vertex in $S(G(F))$ has at most degree
5, and it is in exactly one triangle, $S(G(F))$ is $K_{1,5}$-free (also,
($K_{4}$, diamond, butterfly,$K_{1,5}$)-free implies maximum degree 5).

Next, let us show that $S(G(F))$ is ($H$,snail,press)-free.

Suppose $S(G(F))$ has a snail as an induced subgraph. The triangle of the
snail should be a vertex triangle since one of its vertices has degree at
least 4. But in this case, this triangle has at most one simplicial vertex
which is a contradiction. Hence, $S(G(F))$ is snail-free.

If $S(G(F))$ has an $H$ as an induced subgraph. We consider two cases: (i) the
middle edge is part of some triangle $T$ and clearly, $T$ is a vertex
triangle, again $T$ has at most one simplicial vertex (ii) the middle edge
connects two triangles, one of them is a clause triangle meaning that one of
the middle vertices should have degree exactly 3. All its three neighbors are
in $H$ and there is not any triangle, a contradiction. Therefore, $S(G(F))$ is
$H$-free.

Suppose now that $S(G(F))$ contains a press as an induced subgraph. Clearly,
one of the two triangles must be a variable triangle but both of them have at
most one simplicial vertex. Again, a contradiction. So, $S(G(F))$ is press-
free.

Next we analyse the possible induced cycles of $S(G(F))$ and $G(F)$.

Let $C$ be an induced cycle of $S(G(F))$ having length greater than 3. We
claim that the length of $C$ is reduced by 2/3, in relation to its
corresponding length in $G(F)$. To show this claim, consider a cycle of $G(F)$
and its corresponding cycle of $S(G(F))$. Let $t$ and $k$ represent the
lengths of these cycles of $G(F)$ and $S(G(F))$, respectively. Recall that
$G(F)$ is planar, $C_{4}$-free and bipartite, whose parts are formed by circle
vertices and rectangle vertices, respectively.

In $G(F)$ each rectangle vertex has degree exactly 3 because each clause is
formed by 3 positive literals. Furthermore, each of these rectangle vertices
is replaced by a clause triangle. To extend $T(G(F))$, into $S(G(F))$ we add
two new adjacent vertices for each circle vertex $u$, both to be adjacent to
$u$. Therefore, the vertices belonging to an induced cycle of length $\geq 4$
in $S(G(F))$ are circle vertices, and vertices of clause triangles. Clearly,
they ought to be these both types, since the set of circle vertices form an
independent set, while the clause triangles are disjoint triangles. Clearly,
we need at least two circle vertices, to form an induced cycle $C$ of
$S(G(F))$. For each such circle vertex, we need two vertices of clause
triangles. Therefore, if $C$ contains $t$ circle vertices, $C$ also contains
another $2t$ vertices from clause triangles, that is $3t$ vertices in total.
Next, every pair of vertices of clause triangles is contracted into a single
vertex. Therefore, $t=(2/3)k$, and the length of each cycle of $G(F)$ becomes
2/3 smaller, indeed.

As $G(F)$ is bipartite and $C_{4}$-free, the only values available for $k$ is
$3t$ with $t\geq 3$. Therefore, $S(G(F))$ and $T(G(F))$ are
($C_{4}$,$C_{5}$,$C_{6}$,$C_{7}$,$C_{8}$,$C_{3t+1}$,$C_{3t+2}$)-free, for
$t\geq 3$.

As $G(F)$ is planar, take a planar representation of $G(F)$, any vertex is
replaced by a triangle. In case of a variable triangle, it is clear that the
two adjacent new neighbors of the circle vertex maintain the planar
representation (see Figure 6). In case of a clause triangle, a similar fact
holds (see Figure 5). Therefore, $S(G(F))$ is planar. ∎

$C_{i}$$X_{1}$$X_{2}$$X_{3}$ | $X_{1}$$X_{2}$$X_{3}$
---|---
Figure 5: Replacing a clause by a triangle $X_{i}$$C_{1}$$C_{2}$$C_{3}$ | $C_{1}$$C_{2}$$C_{3}$
---|---
Figure 6: Replacing a variable by a triangle

######  Theorem 5.

There is a valid assignment for an input formula $F$ of Subcubic planar
$C_{4}$-free positive 1in3SAT if and only if the resulting graph $S(G(F))$ of
the main transformation contains some dominating induced matching.

###### Proof.

Given a valid assignment, we define a bi-coloring of $S(G(F))$ using this
assignment below.

  1. 1.

if a variable $x_{i}$ is true then color black its corresponding circle vertex
$v$. Choose arbitrarily any neighbor $w$ of its variable triangle and color it
also black. Color white all other neighbors of $v$.

  2. 2.

if a variable $x_{i}$ is false then color white its corresponding circle
vertex $v$ and color black all its neighbors.

Next we prove that this bi-coloring verifies the conditions of Theorem 1.

  1. 1.

In a variable triangle, every vertex satisfies trivially the conditions.

  2. 2.

In a clause triangle, a vertex is colored black (white) if its unique circle
vertex neighbor $x_{i}$ is colored white (black) because the variable $x_{i}$
is false (true). As every clause has one true literal (all literals are
positive). In any clause triangle $T$, there is exactly one white vertex $v$
and all its 3 neighbors have been colored black. Particularly, the other two
vertices of $T$.

Therefore, this bi-coloring corresponds to a DIM of $S(G(F))$.

Conversely, given a DIM $D$ and its associated bi-coloring, we define an
assignment as follows. If a circle vertex $x_{i}$ is black (white) then the
variable $x_{i}$ is true (false). We will prove this assignment is valid.
Using the properties of Theorem 2 and considering $T$ the variable triangle
that contains $x_{i}$, every clause triangle neighbor $w$ of $v$ has a
different color of $x_{i}$ since the vertices of $T$ and $w$ induce a paw and
$x_{i},w$ are the odd degree vertices in the induced paw. The color of $w$ is
white only if $x_{i}$ is true. As every clause triangle has exactly one white
vertex. Consequently, every clause has exactly one true literal. ∎

######  Corollary 1.

EXISTENCE DIM is NP-Complete for planar neighborhood-star-free
($K_{4}$,diamond,butterfly,$K_{1,5}$,$H$,snail,press,$C_{4}$,$C_{5}$,$C_{6}$,$C_{7}$,$C_{8}$,$C_{3t+1}$,
$C_{3t+2}$)-free graphs for $t\geq 3$ without pendant vertices.

Since neighborhood-star-free graphs do not have proper perfect dominating
sets, the existence of DIM is equivalent to ask if exist a perfect edge
dominating set with at most $m-1$ edges where $|E|=m$ (the trivial perfect
dominating set is the set of all edges $E$).

######  Corollary 2.

EXISTENCE of perfect dominating set with at most $m-1$ edges is NP-Complete
for Planar neighborhood-star-free ($K_{4}$,diamond,butterfly,
$K_{1,5}$,$H$,snail,press,$C_{4}$,$C_{5}$,$C_{6}$,$C_{7}$,$C_{8}$,$C_{3t+1}$,$C_{3t+2}$)-free
graphs for $t\geq 3$ without pendant vertices where $m$ is the number of edges
in the graph.

A _subdivision_ of an edge $(v,w)$ in a graph consists of replacing such edge
by two edges $(v,u),(u,w)$ and a new vertex $u$.

######  Lemma 2.

[11] Let $G$ be a graph and $e$ an edge in $G$. If $G^{\prime}$ is the graph
obtained from $G$ by subdividing the edge $e$ exactly three times, then $G$
has a dominating induced matching if and only if so has $G^{\prime}$.

Cardoso, et al. [11] use the ideas of the triple subdivision of the edges (see
Lemma 2) to extend the girth of the graph without affecting the existence or
not of DIM. This technique does not work for our class under consideration
since this operation adds 3 new vertices of degree 2 and they are not part of
triangles. Instead of this operation we propose other alternatives to avoid
induced cycles of size at most $k$ for any $k$. But all of them come with some
cost. The main idea is replacing edges of $S(G(F))$, the resulting graph of
Main Transformation that connects vertices of different triangles by chains of
structures that assure the vertices at both ends of chains should have
different colors in any valid bi-coloring. We call those edges as variable-
clause edges since they connect a variable triangle to a clause triangle. It
is clear that every vertex of the chains should be in a triangle. We define
two types of triangles: (i) vertex link triangles, these triangles have only
one vertex in the chain, and (ii) edge link triangles, which are those that
have exactly two vertices in the chain. There are many alternatives to create
chains.

  1. 1.

Every chain has exactly $2k_{1}$ vertex link triangles (see Figure 7 for
$k_{1}=1$). It is clear that every pair of consecutive vertices in the chain
are odd-degree vertices in some induced paw. By Theorem 2, they have different
colors in any valid bi-coloring. Since the chain has $2k_{1}+1$ edges, then
both ends of the chain have different colors in any valid bi-coloring.

variableclause | variableclause
---|---
Figure 7: Replacing a variable-clause edge by a chain of 2 vertex link
triangles

  2. 2.

Every chain has alternatively edge link triangles and vertex link triangles if
we started from the variable triangle side, the first triangle is an edge link
triangle. The number of each type of triangle is $2k_{2}$ (see Figure 8 for
$k_{2}=1$). Some additional structure is needed for edge link triangles. Each
edge link triangle has exactly one vertex that is not in the chain. We should
connect this vertex to some contact vertex of a gadget. There are three
options for the gadget structure (see Figure 8).

    1. (a)

A butterfly, where the contact vertex is its central vertex.

    2. (b)

A $K_{1}$ and the contact vertex is the unique one. This vertex will become a
pendant vertex.

    3. (c)

A diamond, where the contact vertex is any vertex of degree 2 in the diamond.

variableclause | variableclause
---|---

(a) butterfly(b) pendant(c) diamond

Figure 8: Replacing a variable-clause edge by a mixed chain of 2 vertex link
triangles and 2 edge link triangles and 3 options for gadget

In any case, the contact vertex is colored white in any valid bi-coloring by
Theorem 2 and its neighbor in the edge link triangle should be black, again by
Theorem 2. In consequence, the vertices of the edge link triangle in the chain
should have different colors. All other edges of the chain form part of some
induced paw and their incident vertices have degree odd in such paw.
Therefore, every pair of consecutive vertices in the chain have different
colors in any valid bi-coloring. The number of edges in the chain is exactly
$6k_{2}+1$, an odd number, which implies that both ends of the chain have a
different color in any valid bi-coloring.

It is clear that $S(G(F))$ admits a DIM if and only if the resulting graph
$Q$, after the replacement of variable-clause edges by the chains described
above, has a DIM. Furthermore, every variable-clause edge of $S(G(F))$ is part
of some induced paw and its incident vertices have odd degree in such induced
paw. Consequently, they should have different colors in any valid bi-coloring,
by Theorem 2. Then from any valid bi-coloring of $Q$, we can obtain trivially
a valid bi-coloring of $S(G(F))$. Conversely, any valid bi-coloring of
$S(G(F))$, can be extended easily to a bi-coloring of $Q$. Consequently, we
can define new reductions from Subcubic planar $C_{4}$-free positive 1in3SAT
to the DIM problem, concatenating the Main Transformation and one of these
types of replacement of variable-clause edges.

Next, let us examine the resulting graph class of each type of replacement.
The number of variable-clause edges in an induced cycle in $S(G(F))$ is at
least 6 and the number of clause triangle edges is at least 3 since the
induced cycles in the associated graph $G(F)$ have at least 3 clause vertices.

  1. 1.

In this case, the only forbidden subgraph of Corollaries 1 and 2 that can
appear is the $H$ graph. All induced cycles of $Q$ should have at least
$6\cdot(2k_{1}+1)+3=12k_{1}+9$ vertices. The number of vertices of $Q$ is
$n+(m-n)\cdot 3\cdot 2k_{1}=6k_{1}m-(6k_{1}-1)\cdot n$ and $Q$ has
$m+(m-n)\cdot 4\cdot 2k_{1}=(8k_{1}+1)\cdot m-8k_{1}n$ edges.

  2. 2.

Independently of the gadget employed, all induced cycles of $Q$ should have at
least $6\cdot(3\cdot 2k_{2}+1)+3=36k_{2}+9$ vertices.

    1. (a)

In this case, the only forbidden subgraph of Corollaries 1 and 2 that can
appear is the butterfly. The number of vertices of $Q$ is
$n+(m-n)\cdot(8+3)\cdot 2k_{2}=22k_{2}m-(22k_{2}-1)\cdot n$ and $Q$ has
$m+(m-n)\cdot(11+4)\cdot 2k_{2}=(30k_{2}+1)\cdot m-30k_{2}n$ edges.

    2. (b)

In the present situation, $Q$ has pendant vertices. The number of vertices of
$Q$ is $n+(m-n)\cdot(4+3)\cdot 2k_{2}=14k_{2}m-(14k_{2}-1)\cdot n$ and $Q$ has
$m+(m-n)\cdot(5+4)\cdot 2k_{2}=(18k_{2}+1)\cdot m-18k_{2}n$ edges.

    3. (c)

The only forbidden subgraph of Corollaries 1 and 2 that can appear is the
diamond. We remark that there are no gems, nor $W_{4}$’s. The number of
vertices of $Q$ is $n+(m-n)\cdot(7+3)\cdot 2k_{2}=20k_{2}m-(20k_{2}-1)\cdot n$
and $Q$ has $m+(m-n)\cdot(10+4)\cdot 2k_{2}=(28k_{2}+1)\cdot m-28k_{2}n$
edges.

Also, in any case, $Q$ will still be a planar graph of degree at most five. We
remark that cycles of size between $4$ and $k$, in $Q$, for fixed $k\geq 4$,
are forbidden. For each type of replacement, we can determine the smallest
required value of $k_{1}$ or $k_{2}$ to assure this.

######  Theorem 6.

For any fixed value $k\geq 4$, EXISTENCE DIM and EXISTENCE of perfect
dominating set with at most $m-1$ edges are NP-Complete in the following graph
classes.

  * •

Planar neighborhood-star-free
($K_{4}$,diamond,butterfly,$K_{1,5}$,snail,press,$C_{4},$ $\dots,C_{k}$)-free
without pendant vertices.

  * •

Planar neighborhood-star-free ($K_{4}$,diamond,$K_{1,5}$,$H$,snail,press,
$C_{4},\dots,C_{k}$) -free without pendant vertices.

  * •

Planar neighborhood-star-free ($K_{4}$,diamond,butterfly,$K_{1,5}$,$H$,snail,
press,$C_{4},$ $\dots,C_{k}$)-free.

  * •

Planar neighborhood-star-free
($K_{4}$,gem,$W_{4}$,butterfly,$K_{1,5}$,$H$,snail, press,$C_{4},$
$\dots,C_{k}$)-free without pendant vertices.

##  3 NSF graphs, with no crickets

In this section, we describe a polynomial time algorithm for finding a DIM, if
existing, of an NSF graph $G$, with no crickets.

The idea of the algorithm is to color the vertices of $G$ with two colors,
black (B) and white (W), to satisfy Lemma 3, or otherwise conclude that no
such coloring exists. According to that lemma, this is sufficient to determine
a DIM of $G$ or inform that it does not exist.

The algorithm is divided into phases:

###  3.1 Discharging Phase

If $G$ contains a $K_{4}$, $W_{4}$, or gem as an induced subgraph then $G$
does not contain a DIM.

###  3.2 Pre-coloring Phase

Find a pre-coloring of the vertices of G, by iteratively applying the
following rules:

  1. 1.

(a) If $G$ contains a butterfly, then apply color $W$ to the (unique) vertex
of degree 4 and apply color $B$ to the four remaining vertices of the
butterfly.

  2. 2.

(b) If $G$ contains a diamond, then use $B$ to color the two vertices of
degree 3 of the diamond, and apply color $W$ to the other two, which have
degree 2.

  3. 3.

(c) Apply color $B$ to the unique neighbor of each 1-degree vertex in $G$
(preleaves vertices must be black).

  4. 4.

(d) Apply color $W$ to the vertices of 0-degree in $G$

###  3.3 Propagation Phase

Next we apply propagation rules. That is, we try to extend the pre-coloring so
far obtained, to some other vertices, according to the following steps:

  1. 1.

(e) In a paw, the two vertices of odd degree ought to have different colors.
So, if just one of them is so far colored, then color the second one, so as to
have a different color from the first one.

  2. 2.

(f) Each vertex colored with $B$ must have exactly one neighbor colored $B$,
So, if a black vertex $v$ has already a black neighbor, then apply the white
color $W$ to all other neighbors of $v$.

  3. 3.

(g) All neighbors of a white vertex must be black. Then apply the color $B$ to
all neighbors of any white vertex.

  4. 4.

(h) If a vertex $v$ has two black neighbors then $v$ must be white. Then apply
the white $(W)$ to any vertex $v$ having two neighbors with color $B$.

###  3.4 Applying the Phases

Apply the above phases, according to:

  1. 1.

Apply the Discharging Phase to $G$. If the graph contains a $K_{4}$, $W_{4}$
or gem then answer that $G$ does not contain a DIM and terminate the
algorithm.

  2. 2.

Apply the Pre-coloring Phase, Rules (a)-(d). In case some vertex gets colored
with both colors $B$ and $W$, then $G$ does not contain a DIM and terminate
the algorithm. Next, verify if the (partial) coloring so far obtained is
valid, by applying the Definition 1. In case that the coloring is not valid
then $G$ does not contain a DIM and terminate the algorithm.

  3. 3.

Iteratively, apply the Propagation Phase, Rules (e)-(h), until no further
colorings are obtained. As before, if any vertex gets both colors, $B$ and
$W$, then $G$ does not contain a DIM, and terminate the algorithm.

  4. 4.

Verify if the coloring obtained by the previous phases is total, that is, if
all vertices have been colored. In the affirmative case, the algorithm has
obtained a DIM, which is precisely the DIM associated to that (total)
coloring, and terminate the algorithm. Otherwise, the coloring is just
partial, and we proceed with the algorithm.

######  Lemma 3.

After the execution of the Propagation Phase for an $NSF$ graph $G$, exactly
one of the following alternatives apply:

  1. 1.

A (valid) total coloring has been found. In this case, a $DIM$ has been
obtained (which is the unique DIM of $G$), and terminate the algorithm.

  2. 2.

Either an invalid coloring has been found, or some vertex has been assigned
two both (distinct) colors. In this situation, $G$ does not contain a $DIM$,
and terminate the algorithm.

  3. 3.

A partial valid coloring has been found. In this alternative, the algorithm
proceeds.

The proof of the lemma is straightforward.

Next we describe the actions to be taken for completing the coloring, in
Alternative (3) of the previous lemma.

The next lemma describes the vertices that are still uncolored and the
triangles that contain at least one of these so far uncolored vertices.

######  Lemma 4.

Let $v\in V$ be a vertex of $G$, that remained uncolored after the execution
of the end of the Propagation Phase of the algorithm. Then:

  * •

(i): Vertex $v$ has at most one colored neighbor $u$. In that case, $u$ must
be black and has no black neighbors.

  * •

(ii): Vertex $v$ has degree at least 2. In this case, $v$ is contained in a
triangle. The three vertices of a such triangle satisfy either:
\- All of them are uncolored (_Triangle Type 1_), or
\- One of the neighbors of $v$ is black, and the other two are uncolored.
(_Triangle Type 2_)

###### Proof.

Part (i) follows from the _(_ Propagation Phase). Next, examine Part (ii):

Since $G$ is an NSF graph, if a vertex $v$ has degree $\geq 2$ then $v$
belongs to a triangle. Then, the only vertices which are not part of a
triangle have degree $\leq 1$. Those of degree $0$ are necessarily white,
according to Rule (d) of the _Pre-coloring Phase_.

Next, examine the vertices of degree 1, and let $v$ be such a vertex, and $u$
its only neighbor.

By Rule (c), $u$ is black. Additionally, if the degree of $u$ is also 1, for
this same reason, $v$ must also be black.

Consequently, if $v$ was still uncolored up to this point, then $u$ must be
contained in some triangle $T$.

Clearly, $G[T\cup\\{v\\}]$ is a paw, and $v,u$ have odd degree in this paw.

By Rule (e) of the Propagation Phase, since $u$ is black, it follows that $v$
is white, a contradiction.

Consequently, all vertices of degree $\leq 1$ have been colored.

Next, consider the collection of triangles that contain some uncolored vertex.
Each of these triangles either contains all its three uncolored vertices (Type
1), or two uncolored ones (Type 2, the unique colored vertex of a triangle of
this type must be black and does not have any black neighbor in $G$, otherwise
all vertices of the triangle should have been colored which is a
contradiction).

We know that no pair of such triangles can have a common vertex. Otherwise,
these two triangles would induce a diamond, a butterfly, or a $K_{4}$.

In case of a diamond or a butterfly, according to Rules (e) and (f) of the
Propagation Phase, these vertices have been already colored, a contradiction.
Finally, in case of a $K_{4}$, the algorithm has already terminated, by the
Discharging Phase. ∎

We still need to analyze the triangles, of both Types 1 and 2, that contain at
least one of the uncolored vertices.

Let $G^{\prime}$ denote the subgraph of $G$ induced by those vertices
contained in the triangles of Types 1 and 2. The following lemma describes
$G^{\prime}$, assuming that $G$ is cricket-free.

######  Lemma 5.

If $G$ is NSF cricket-free then

  * •

(i): $G^{\prime}$ is subcubic and claw-free.

  * •

(ii) The still uncolored vertices of $G$, together with their colored
neighbors of triangles of Type 2, all lie in $G^{\prime}$.

  * •

(iii) Each uncolored vertex $u$ of $G^{\prime}$ satisfies either one of the
following conditions:

    1. 1.

$u$ has degree 2, and its neighbors are adjacent.

    2. 2.

$u$ has degree 3, and exactly two of its three neighbors are adjacent.

  * •

(iv) $G^{\prime}$ admits a total valid coloring.

###### Proof.

(ii) It follows directly from the definition $G^{\prime}$.

(i) If the degree of $u$ is at least 4, then $u$ has two neighbors outside the
considered triangle $T$. Then these two neighbors, together with the three
vertices of $T$, induce a cricket. However, $G$ is cricket-free, a
contradiction. Therefore, the vertices of $G^{\prime}$ have degree at most 3
and induce no claws.

(iii) It follows from (i) and (ii).

(iv) It follows from Lemma 1. ∎

Consequently, we can apply the graph $G^{\prime}$ to the the algorithm
described in [18], which obtains a DIM of $G^{\prime}$ in $O(n)$ time.

###  3.5 Description of the Algorithm

Following the above description, the algorithm can now be summarized as
follows: Let $G$ be the input graph. The algorithm is divided into parts:

  1. 1.

PART:1 Recognition of $G$
To recognize if $G$ is an NSF graph, for each vertex $v$ of $G$, verify if the
subgraph induced by the open neighborhood of $v$ has at least one edge. In the
affirmative case, $G$ is indeed NSF otherwise it is not. Terminate the
algorithm in the negative case. Next, verify if $G$ is cricket-free, by
looking at all its induced subgraphs of 5 vertices. Again, proceed if positive
and terminate when negative.

  2. 2.

PART 2: RUNNING THE PHASES:
Perform the four steps, as described in Subsection 3.4.That is,

     * •

Apply the Discharging Phase

     * •

Apply Rules a-d of the Pre-coloring Phase

     * •

Apply Rules e-h of the Propagation Phase

     * •

Apply the verification step 4 of Subsection 3.4.

If the algorithm did not so far stop, either because a DIM has already been
found, or because it does not exist, then proceed to PART 3.

  3. 3.

PART 3: Construction of graph $G^{\prime}$
Consider the triangles of $G$ containing still uncolored vertices. Partition
these triangles into two types:
Type 1: All three of their vertices are uncolored.
Type 2: These triangles contain exactly two uncolored vertices, each.
Let $G^{\prime}$ be the subgraph induced by the vertices of triangles of Types
1 and 2.

  4. 4.

PART 4: Finding the DIM
Find the DIM of the graph of $G^{\prime}$, employing the algorithm [18], which
completes the solution of our initial problem.

###  3.6 Complexity of the Algorithm

To verify the complexity of the algorithm, follow the 4 parts of its
description. For Part 1, checking if $G$ is NSF requires no more than $O(nm)$
time, by the procedure described. As for verifying if $G$ is cricket-free, we
need $O(n^{5})$ time, using a brute-force method for going through all induced
subgraphs of size 5. For Part 2, there are 4 checks to be made:
The Discharging Phase requires $O(n^{5})$ time, again using brute-force to
generate all subgraphs of sizes 4 and 5.
The Pre-coloring Phase requires $O(n^{5})$ time since its time-dominating
operation is to generate all induced subgraphs of 5 vertices, again employing
a brute-force method.
The operations of the Propagation Phase can be done, altogether, in $O(n^{5})$
time. That is, each of the iterated executions can be accomplished in
$O(n^{4})$ time, since its time dominating operation is listing all 4-induced
subgraphs, for looking for paws. Moreover, at most $O(n)$ iterations are
needed since we stop when every vertex has been colored. Therefore, this Part
can be implemented in $O(n^{5})$ time.
For Part 3, we generate all triangles of $G$ and find those of Parts 1 and 2.
These operations can be done easily in $O(n^{3})$ time, Finally, for Part 4,
we employ the algorithm of [18], which can be implemented in $O(n)$ time.
Therefore, the entire algorithm requires no more than $O(n^{5})$ time.

By employing more efficient techniques, using convenient data structures for
generating all the required induced subgraphs, we estimate that the running
time of the algorithm can be decreased to $O(nm)$. We leave to the readers the
task of describing the details of this implementation.

##  4 Conclusions

We conclude with an open question.

We wonder if there is some algorithmic relation between efficient and perfect
edge domination. More specifically, we remark that there are graph classes
which admit polynomial time solutions for solving the efficient edge
domination problem while being hard for solving the perfect edge domination
problem. However, we ask whether there is some graph class for which there
exists a polynomial time algorithm for solving the perfect edge domination
problem while being hard for the efficient edge domination problem.

## Acknowledgements

Min Chih Lin was partially supported by UBACyT Grants 20020190100126BA and
20020170100495BA, and CONICET grant PIP 11220200100084CO, Argentina. Abilio
Lucena acknowledges the support of CNPq grant 309887/2018-6, Brazil Nelson
Maculan was partially supported by CNPq and COPPETEC Foundation, Brazil.
Veronica A. Moyano was partially supported by Universidad Nacional de General
Sarmiento grant 30/1135, Argentina. Jayme L. Szwarfiter was partially
supported by FAPERJ and CNPq, Brazil.

## References

  * [1] A. Brandstädt, C. Hundt, R. Nevries, Efficient edge domination on hole-free graphs in polynomial time, in: LATIN 2010: theoretical informatics, Vol. 6034 of Lecture Notes in Comput. Sci., Springer, Berlin, 2010, 650–661.
  * [2] A. Brandstädt, Efficient domination and efficient edge domination: a brief survey, in: Algorithms and discrete applied mathematics, Vol. 10743 of Lecture Notes in Comput. Sci., Springer, Cham, 2018, 1–14.
  * [3] A. Brandstädt, R. Mosca, Dominating induced matchings for $P_{7}$-free graphs in linear time, Algorithmica 68 (4) (2014), 998–1018.
  * [4] A. Brandstädt, R. Mosca, Finding dominating induced matchings in $P_{8}$-free graphs in polynomial time, Algorithmica 77 (4) (2017), 1283–1302.
  * [5] A. Brandstädt, R. Mosca, Dominating induced matchings in $S_{1,2,4}$-free graphs, Discrete Appl. Math. 278 (2020), 83–92.
  * [6] A. Brandstädt, R. Mosca, Finding dominating induced matchings in $S_{2,2,3}$-free graphs in polynomial time, Discrete Appl. Math. 283 (2020), 417–434.
  * [7] A. Brandstädt, R. Mosca, Finding dominating induced matchings in $S_{1,1,5}$-free graphs in polynomial time, Discrete Appl. Math. 284 (2020), 269–280.
  * [8] A. Brandstädt, R. Nevries, Efficient dominating and edge dominating sets for graphs and hypergraphs, in: Encyclopedia of Algorithms, 2016, pp. 618–621.  doi:10.1007/978-1-4939-2864-4\\_689.
URL https://doi.org/10.1007/978-1-4939-2864-4_689

  * [9] A. Brandstädt, A. Leitert, D. Rautenbach, Efficient dominating and edge dominating sets for graphs and hypergraphs, in: K. Chao, T. Hsu, D. Lee (Eds.), Algorithms and Computation - 23rd International Symposium, ISAAC 2012, Taipei, Taiwan, December 19-21, 2012. Proceedings, Vol. 7676 of Lecture Notes in Computer Science, Springer, 2012, pp. 267–277.  doi:10.1007/978-3-642-35261-4\\_30.
URL https://doi.org/10.1007/978-3-642-35261-4_30

  * [10] D. M. Cardoso, J. O. Cerdeira, C. Delorme, P. C. Silva, Efficient edge domination in regular graphs, Discrete Applied Mathematics 156 (15) (2008), 3060–3065.
  * [11] D. M. Cardoso, N. Korpelainen, V. V. Lozin, On the complexity of the dominating induced matching problem in hereditary classes of graphs, Discrete Applied Mathematics 159 (7) (2011), 521–531.  doi:https://doi.org/10.1016/j.dam.2010.03.011.
  * [12] V. L. do Forte, M. C. Lin, A. Lucena, N. Maculan, V. A. Moyano, J. L. Szwarcfiter, Modelling and solving the perfect edge domination problem, Optim. Lett. 14 (2020), 369–394.
  * [13] D. L. Grinstead, P. J. Slater, N. A. Sherwani, N. D. Holmes, Efficient edge domination problems in graphs, Inform. Process. Lett. 48 (5) (1993), 221–228.  doi:10.1016/0020-0190(93)90084-M.
URL https://doi.org/10.1016/0020-0190(93)90084-M

  * [14] A. Hertz, V. Lozin, B. Ries, V. Zamaraev, D. de Werra, Dominating induced matchings in graphs containing no long claw, J. Graph Theory 88 (1) (2018), 18–39.
  * [15] N. Korpelainen, V. V. Lozin, C. Purcell, Dominating induced matchings in graphs without a skew star, J. Discrete Algorithms 26 (2014), 45–55.  doi:10.1016/j.jda.2013.11.002.
URL https://doi.org/10.1016/j.jda.2013.11.002

  * [16] M. C. Lin, V. Lozin, V. A. Moyano, J. L. Szwarcfiter, Perfect edge domination: Hard and solvable cases, Annals of Operations Research 264 (2018), 287–305.  doi:https://doi.org/10.1007/s10479-017-2664-3.
  * [17] M. C. Lin, M. J. Mizrahi, J. L. Szwarcfiter, Exact Algorithms for Minimum Weighted Dominating Induced Matching, Algorithmica 77 (3) (2017), 642–660.  doi:https://doi.org/10.1007/s00453-015-0095-6.
  * [18] M. C. Lin, M. J. Mizrahi, J. L. Szwarcfiter, Fast algorithms for some dominating induced matching problems, Information Processing Letters 114 (10) (2014) 524–528.  doi:https://doi.org/10.1016/j.ipl.2014.04.012.
  * [19] C. L. Lu, M.-T. Ko, C. Y. Tang, Perfect edge domination and efficient edge domination in graphs, Discrete Applied Mathematics 119 (3) (2002), 227–250.  doi:https://doi.org/10.1016/S0166-218X(01)00198-6.
  * [20] C. L. Lu, C. Y. Tang, Solving the weighted efficient edge domination problem on bipartite permutation graphs, Discrete Applied Mathematics 87 (1) (1998), 203–211.  doi:https://doi.org/10.1016/S0166-218X(98)00057-2.
URL https://www.sciencedirect.com/science/article/pii/S0166218X98000572

  * [21] C. Moore, J. Robson, Hard tiling problems with simple tiles, Discrete & Computational Geometry 26 (2001), 573–590.  doi:10.1007/s00454-001-0047-6.
  * [22] V. Moyano, Edge dominating set problems: Algorithms, bounds and properties, Ph.D. thesis, Universidad de Buenos Aires (2017).
  * [23] R. Nevries, Efficient domination and polarity, Ph.D. thesis, University of Rostock (2014).