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

DOI10.1016/J.ENDM.2015.07.031MaRDI QIDQ324774zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

• scientific article; zbMATH DE number 1375569 (Why is no real title available?)
• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• Linear time solvable optimization problems on graphs of bounded clique-width
• On a new class of codes for identifying vertices in graphs
• On the structure of graphs with few P₄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)