Efficient edge domination in regular graphs
| Data(s) |
28/11/2011
2008
|
|---|---|
| Resumo |
An induced matching of a graph G is a matching having no two edges joined by an edge. An efficient edge dominating set of G is an induced matching M such that every other edge of G is adjacent to some edge in M. 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 ≥ 3, deciding on the existence of efficient edge dominating sets on p-regular graphs is NP-complete. © 2008 Elsevier B.V. All rights reserved. CEOC FCT FEDER/POCI 2010 POCTI Program |
| Identificador |
0166-218X |
| Idioma(s) |
eng |
| Publicador |
Elsevier |
| Relação |
http://www.scopus.com/inward/record.url?eid=2-s2.0-53049098028&partnerID=40&md5=0ef45737898fdb44f1b1ae81aee6d150 http://www.sciencedirect.com/science/article/pii/S0166218X08000413 |
| Direitos |
restrictedAccess |
| Palavras-Chave | #Domination in graphs #Induced matchings #NP-completeness #Regular graphs #Spectra of graphs #Edge dominating set #Graph theory |
| Tipo |
article |
