Some links between identifying codes and separating, dominating and total dominating sets in graphs

DOI10.1016/J.ENDM.2015.07.031zbMATH Open1347.05148OpenAlexW2211039167MaRDI QIDQ324774FDOQ324774

Authors: P. Torres, G. Nasini 

Publication date: 17 October 2016

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

Recommendations

• Locating-dominating sets and identifying codes in graphs of girth at least 5
• Strong identification codes for graphs
• Decision and approximation complexity for identifying codes and locating-dominating sets in restricted graph classes
• Linear-time algorithms for three domination-based separation problems in block graphs
• Extremal graphs for the identifying code problem

zbMATH Keywords

modular decompositionidentifying code\(P_4\)-tidy graph

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Title not available (Why is that?)
• Linear time solvable optimization problems on graphs of bounded clique-width
• On a new class of codes for identifying vertices in graphs
• Title not available (Why is that?)
• On the structure of graphs with few \(P_4\)s

This page was built for publication: Some links between identifying codes and separating, dominating and total dominating sets in graphs

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