Roman domination in subgraphs of grids

DOI10.1016/J.ENDM.2015.07.014MaRDI QIDQ324726zbMATH OpenOpenAlexFDO

Authors Samuel Nascimento, Rudini M. Sampaio

Publication date 17 October 2016

Full work available at URL https://doi.org/10.1016/j.endm.2015.07.014

zbMATH Keywords

gridRoman dominationAPX-hardfixed parameter tractable

Mathematics Subject Classification ID

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

Recommendations

• Strong Roman domination in grid graphs
• Roman domination in graphs
• scientific article; zbMATH DE number 7366787
• Roman domination in regular graphs
• Roman domination subdivision number of graphs
• Roman lict domination in graphs
• Graph-Theoretic Concepts in Computer Science
• On the Roman domination subdivision number of a graph
• Roman domination in odd and even graphs
• Total roman domination in graphs

Cites work

• scientific article; zbMATH DE number 1330033 (Why is no real title available?)
• A partial k-arboretum of graphs with bounded treewidth
• APPROXIMATING POLYGONS AND SUBDIVISIONS WITH MINIMUM-LINK PATHS
• Diameter and treewidth in minor-closed graph families
• Efficient algorithms for Roman domination on some classes of graphs
• Graph structure and monadic second-order logic. A language-theoretic approach
• Inclusion/exclusion meets measure and conquer
• R<scp>OMAN DOMINATION</scp>: a parameterized perspective†
• Roman domination in graphs.
• The Complexity of Multiterminal Cuts
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• Unit disk graphs

Cited in

(7)

• scientific article; zbMATH DE number 6813626 (Why is no real title available?)
• The 2-domination and Roman domination numbers of grid graphs
• On the computational complexity of Roman\(\{2\}\)-domination in grid graphs
• scientific article; zbMATH DE number 7366787 (Why is no real title available?)
• SOFSEM 2006: Theory and Practice of Computer Science
• R<scp>OMAN DOMINATION</scp>: a parameterized perspective†
• Roman domination and independent Roman domination on graphs with maximum degree three

This page was built for publication: Roman domination in subgraphs of grids

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q324726)