Dominating Induced Matchings for P7-Free Graphs in Linear Time

Andreas Brandstadt, Raffaele Mosca

Let $G$ be a finite undirected graph with edge set $E$. An edge set $E^{\prime }\subseteq E$ is an {\em induced matching} in $G$ if the pairwise distance of the edges of $E^{\prime }$ in $G$ is at…