A polyhedral view to a generalization of multiple domination

Given an undirected simple graph G=(V,E) and integer values fv,v∈V, a node subset D⊆V is called an f-tuple dominating set if, for each node v∈V, its closed neighborhood intersects D in at least fv nodes. We study the polytope that is defined as the convex hull of the incidence vectors in RV of the f...

Full description

Saved in:
Bibliographic Details
Published in:Discrete Applied Mathematics 2022-05, Vol.313, p.1-17
Main Author: Neto, José
Format: Article
Language:English
Subjects:
Computer Science
Convexity
Dominating set
Limited packing
Mathematics
Multiple domination
Polytope
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Given an undirected simple graph G=(V,E) and integer values fv,v∈V, a node subset D⊆V is called an f-tuple dominating set if, for each node v∈V, its closed neighborhood intersects D in at least fv nodes. We study the polytope that is defined as the convex hull of the incidence vectors in RV of the f-tuple dominating sets in G. New families of valid inequalities are introduced and a complete formulation is given for the case of stars. A corollary of our results is a proof that the conjecture reported in Argiroffo (2013) on a complete formulation of the 2-tuple dominating set polytope of trees does not hold. Preliminary computational results are also reported.
ISSN:0166-218X
1872-6771
DOI:10.1016/j.dam.2022.01.011