کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
420520 | 683951 | 2008 | 6 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Efficient edge domination in regular graphs Efficient edge domination in regular graphs](/preview/png/420520.png)
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.
Journal: Discrete Applied Mathematics - Volume 156, Issue 15, 6 August 2008, Pages 3060–3065