DSpace
 
  Repositório Institucional da Universidade de Aveiro > Departamento de Matemática > MAT - Artigos >
 Efficient edge domination in regular graphs
Please use this identifier to cite or link to this item http://hdl.handle.net/10773/4434

title: Efficient edge domination in regular graphs
authors: Cardoso, Domingos M.
Orestes Cerdeira, J.
Delorme, C.
Silva, P. C.
keywords: Domination in graphs
Induced matchings
NP-completeness
Regular graphs
Spectra of graphs
Edge dominating set
Graph theory
issue date: 2008
publisher: Elsevier
abstract: 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.
URI: http://hdl.handle.net/10773/4434
ISSN: 0166-218X
publisher version/DOI: http://www.sciencedirect.com/science/article/pii/S0166218X08000413
source: Discrete Applied Mathematics
appears in collectionsMAT - Artigos

files in this item

file description sizeformat
CardosoCerdeiraDelormeSilva.pdfVersão Electrónica535.63 kBAdobe PDFview/open
Restrict Access. You can Request a copy!
statistics

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

 

Valid XHTML 1.0! RCAAP OpenAIRE DeGóis
ria-repositorio@ua.pt - Copyright ©   Universidade de Aveiro - RIA Statistics - Powered by MIT's DSpace software, Version 1.6.2