Utilize este identificador para referenciar este registo: http://hdl.handle.net/10400.5/5615
Título: Efficient edge domination in regular graphs
Autor: Cardoso, Domingos M.
Cerdeira, J.Orestes
Delorme, Charles
Silva, Pedro C.
Palavras-chave: induced matchings
domination in graphs
regular graphs
NP-completeness
Data: 2008
Editora: Elsevier
Citação: "Discrete Applied Mathematics". ISSN 0166-218X. 156 (2008) 3060-3065
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
Peer review: yes
URI: http://hdl.handle.net/10400.5/5615
ISSN: 0166-218X
Aparece nas colecções:CEF - Artigos de Revistas

Ficheiros deste registo:
Ficheiro Descrição TamanhoFormato 
REP-2008-48.pdf535,63 kBAdobe PDFVer/Abrir


FacebookTwitterDeliciousLinkedInDiggGoogle BookmarksMySpace
Formato BibTex MendeleyEndnote Degois 

Todos os registos no repositório estão protegidos por leis de copyright, com todos os direitos reservados.