On open-separating dominating codes in graphs

DOI10.1016/J.DAM.2025.05.045MaRDI QIDQ6950389zbMATH OpenFDO

Authors Dipayan Chakraborty, Annegret K. Wagler

Publication date 31 July 2025

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.DAM.2025.05.045

zbMATH Keywords

dominating setshypergraphsNP-completenessopen-separating setspolyhedratotal-dominating sets

Mathematics Subject Classification ID

Hypergraphs (05C65) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Combinatorial optimization (90C27) Other types of codes (94B60)

Cites work

• Algorithmic aspects of open neighborhood location-domination in graphs
• Characterizing extremal graphs for open neighbourhood location-domination
• Combinatorial optimization. Packing and covering
• Complexity results on open-independent, open-locating-dominating sets in complementary prism graphs
• Distinguishing-transversal in hypergraphs and identifying open codes in cubic graphs
• Facets and lifting procedures for the set covering polytope
• scientific article; zbMATH DE number 5717189 (Why is no real title available?)
• scientific article; zbMATH DE number 4053685 (Why is no real title available?)
• scientific article; zbMATH DE number 4070954 (Why is no real title available?)
• Identification, location-domination and metric dimension on interval and permutation graphs. I: Bounds.
• Identification, location-domination and metric dimension on interval and permutation graphs. II: Algorithms and complexity
• Induced subsets
• Linear-time algorithms for three domination-based separation problems in block graphs
• Locating and total dominating sets in trees
• Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard.
• On a new class of codes for identifying vertices in graphs
• On open neighborhood locating-dominating in graphs
• On strongly identifying codes
• On the Complexity of Canonical Labeling of Strongly Regular Graphs
• On the facial structure of the set covering polytope
• On the set covering polyhedron of circulant matrices
• On the set covering polytope. I: All the facets with coefficients in \(\{\) 0,1,2\(\}\)
• On three domination-based identification problems in block graphs
• Open locating-dominating sets in circulant graphs
• Open neighborhood locating-dominating in trees
• Open-separating dominating codes in graphs
• Optimal error-detecting open-locating-dominating set on the infinite triangular grid
• Optimal open-locating-dominating sets in infinite triangular grids
• Polyhedra associated with identifying codes in graphs
• Polyhedra associated with locating-dominating, open locating-dominating and locating total-dominating sets in graphs
• Selecting and covering colored points
• The first order definability of graphs: Upper bounds for quantifier depth

This page was built for publication: On open-separating dominating codes in graphs

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