| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 420520 | Discrete Applied Mathematics | 2008 | 6 Pages |
An induced matching of a graph GG is a matching having no two edges joined by an edge. An efficient edge dominating set of GG is an induced matching MM such that every other edge of GG is adjacent to some edge in MM. We relate maximum induced matchings and efficient edge dominating sets, showing that efficient edge dominating sets are maximum induced matchings, and that maximum induced matchings on regular graphs with efficient edge dominating sets are efficient edge dominating sets. A necessary condition for the existence of efficient edge dominating sets in terms of spectra of graphs is established. We also prove that, for arbitrary fixed p≥3p≥3, deciding on the existence of efficient edge dominating sets on pp-regular graphs is NP-complete.
