The complexity of total edge domination and some related results on trees

DOI10.1007/s10878-020-00596-yzbMath1466.05170arXiv1910.02431OpenAlexW3033915607MaRDI QIDQ2023114

Shou-Jun Xu, Zhuo Pan, Yu Yang, Xianyue Li

Publication date: 3 May 2021

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

Full work available at URL: https://arxiv.org/abs/1910.02431

zbMATH Keywords

NP-completenesstreesedge dominationtotal edge domination

Mathematics Subject Classification ID

Trees (05C05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (6)

Algorithms and hardness results for edge total domination problem in graphs ⋮ Nordhaus-Gaddum-type results on the connected edge domination number ⋮ Uncertain Measure and its Application in Minimum Weighted Maximal Matching Problem ⋮ Complexity and characterization aspects of edge-related domination for graphs ⋮ Hamiltonicity of \(3_t\)EC graphs with \(\alpha=\kappa +1\) ⋮ Bounds on total edge domination number of a tree

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the algorithmic complexity of edge total domination
• Two classes of edge domination in graphs
• On covering sets and error-correcting codes
• Minimum Edge Dominating Sets
• Edge Dominating Sets in Graphs
• Edge-Deletion Problems
• Towards a theory of domination in graphs
• Reducibility among Combinatorial Problems

This page was built for publication: The complexity of total edge domination and some related results on trees