Efficient edge domination problems in graphs
type: Item
instance of: scholarly article
title: Efficient edge domination problems in graphs
zbMATH Open document ID: 0797.05076
DOI: 10.1016/0020-0190(93)90084-M
author: Dana L. Grinstead
author: Naveed A. Sherwani
author: Nancy D. Holmes
author: Peter Slater
published in: Information Processing Letters
publication date: 1994-10-10T00:00:00Z
review text: In a graph \(G=(V,E)\), an edge \(uv\in E\) is said to dominate itself and any edge \(ux\) or \(vx\) in \(E\), where \(x\in V\). An efficient edge dominating set for the graph \(G\) is a subset \(E'\subseteq E\) such that all edges in \(E\) are dominated by exactly one edge in \(E'\). It is proved that the efficient edge domination problem is NP-complete for general graphs and also for line graphs. The authors define a series-parallel graph \(G\), denoted by \((G,(u,v))\), to be a graph which has no subgraph homeomorphic to the complete graph \(K_ 4\) and which has two distinguished vertices \(u\) and \(v\) denoted as the left and right terminal of \(G\), respectively. They describe an algorithm which computes the maximum number of edges that can be efficiently dominated in a series-parallel graph in \(O(n)\) time where \(n=| V|\).
Mathematics Subject Classification ID: 05C99
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 500525
zbMATH Keywords: edge domination
zbMATH Keywords: NP-complete
zbMATH Keywords: line graphs
zbMATH Keywords: series-parallel graph
zbMATH Keywords: algorithm
reviewed by: M.Oravas
MaRDI profile type: Publication
cites work: Q3792725
cites work: Q3815323
cites work: Q3941433
cites work: Q3206969
cites work: Perfect codes in graphs
cites work: Graph-theoretic parameters concerning domination, independence, and irredundance
cites work: Towards a theory of domination in graphs
cites work: Q4198056
cites work: A recurrence template for several parameters in series-parallel graphs
cites work: Q3826618
cites work: Q3291034
full work available at URL: 0020-0190(93)90084-m
OpenAlex ID: W2047747666
description: scientific article; zbMATH DE number 500525