Maximum matching and kernelization of edge dominating set

The edge dominating set problem is NP-hard, even when the graph is restricted to planar or bipartite graphs with maximum degree three. In this paper, we prove that in every graph where each vertex is incident to at most one vertex of degree one, the cardinality of maximum matching is at least 2|V|/(3+max⁡(3,Δ(G))). Using the aforementioned result together with a simple reduction rule, we obtain a linear kernel of size 6k for the edge dominating set problem for graphs with maximum degree three.