Complexity and characterization aspects of edge-related domination for graphs

DOI10.1007/s10878-020-00622-zzbMath1472.05121OpenAlexW3042944849MaRDI QIDQ2023127

Xianyue Li, Zhuo Pan, Shou-Jun Xu

Publication date: 3 May 2021

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-020-00622-z

zbMATH Keywords

treesNP-hardnessedge dominationtotal edge dominationsemitotal edge domination

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Extremal problems in graph theory (05C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (2)

Algorithms and hardness results for edge total domination problem in graphs ⋮ Nordhaus-Gaddum-type results on the connected edge domination number

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Edge domination on bipartite permutation graphs and cotriangulated graphs
• Graphs with unique minimum edge dominating sets and graphs with unique maximum independent sets of vertices
• Edge domination in graphs
• On the semitotal domination number of line graphs
• The complexity of total edge domination and some related results on trees
• Two classes of edge domination in graphs
• Minimum Edge Dominating Sets
• Edge Dominating Sets in Graphs
• The Complexity of Multiterminal Cuts
• Reducibility among Combinatorial Problems

This page was built for publication: Complexity and characterization aspects of edge-related domination for graphs