On the mixed domination problem in graphs

DOI10.1016/j.tcs.2012.11.035zbMath1261.05079OpenAlexW2070924562MaRDI QIDQ1945934

James K. Lan, Gerard Jennhwa Chang

Publication date: 17 April 2013

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2012.11.035

zbMATH Keywords

treetreesNP-completesplit graphscactuslinear time labeling algorithmmixed dominating setmixed domination problem

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (14)

Improved Budgeted Connected Domination and Budgeted Edge-Vertex Domination ⋮ Mixed domination and 2-independence in trees ⋮ On the algorithmic complexity of edge total domination ⋮ Signed mixed Roman domination numbers in graphs ⋮ Mixed Roman domination in graphs ⋮ \([1,2\)-sets and \([1,2]\)-total sets in trees with algorithms] ⋮ On the complexity of variations of mixed domination on graphs^† ⋮ Unnamed Item ⋮ Improved budgeted connected domination and budgeted edge-vertex domination ⋮ An efficient algorithm for distance total domination in block graphs ⋮ The strong domination problem in block graphs and proper interval graphs ⋮ Upper and lower bounds on approximating weighted mixed domination ⋮ Improved parameterized algorithms and kernels for mixed domination ⋮ Signed mixed dominating functions in complete bipartite graphs

This page was built for publication: On the mixed domination problem in graphs