A polyhedral approach to locating-dominating sets in graphs

DOI10.1016/j.endm.2015.07.016zbMath1347.05135OpenAlexW2203809600MaRDI QIDQ324734

Annegret K. Wagler, Silvia M. Bianchi, Gabriela R. Argiroffo

Publication date: 17 October 2016

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

zbMATH Keywords

set coveringlocating-dominating setfacet-descriptions of polyhedra

Mathematics Subject Classification ID

Small world graphs, complex networks (graph-theoretic aspects) (05C82) Polytopes and polyhedra (52B99) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (5)

The identifying code, the locating-dominating, the open locating-dominating and the locating total-dominating problems under some graph operations ⋮ Linear-time algorithms for three domination-based separation problems in block graphs ⋮ On locating-dominating set of regular graphs ⋮ Polyhedra associated with locating-dominating, open locating-dominating and locating total-dominating sets in graphs ⋮ Locating-dominating sets of functigraphs

Cites Work

• Unnamed Item
• Unnamed Item
• On the facial structure of the set covering polytope
• Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard.
• Identifying and locating-dominating codes on chains and cycles
• Locating and total dominating sets in trees
• Domination and location in acyclic graphs

This page was built for publication: A polyhedral approach to locating-dominating sets in graphs