The 2-doinating set polytope of cycles and related graphs classes

ARGIROFFO, GABRIELA; ESCALANTE, MARIANA SILVINA; UGARTE, MARIA ELISA

Playa del Carmen

Simposio; LAGOS 2013- VII Latin American Algorithms, Graphs and Optimization Symposium; 2013

Given a graph G and a nonnegative integer number k, a k-dominating set in G is a subset of vertices D such that every vertex in the graph is adjacent to at least kG and a nonnegative integer number k, a k-dominating set in G is a subset of vertices D such that every vertex in the graph is adjacent to at least kD such that every vertex in the graph is adjacent to at least k elements of D. The k-dominating set polytope is the convex hull of the incidence vectors of k-dominating sets in G. This is a natural generalization of the well-known dominating set polytope in graphs. In this work we present a complete description of the 2-dominating set polytope of cycles and show that every facet of this polytope can be separated in polynomial time. We use our ndings to derive facets of the 2-dominating set polytope of cacti, i.e. graphs obtained as 1-sum of cycles and edges.D. The k-dominating set polytope is the convex hull of the incidence vectors of k-dominating sets in G. This is a natural generalization of the well-known dominating set polytope in graphs. In this work we present a complete description of the 2-dominating set polytope of cycles and show that every facet of this polytope can be separated in polynomial time. We use our ndings to derive facets of the 2-dominating set polytope of cacti, i.e. graphs obtained as 1-sum of cycles and edges.k-dominating sets in G. This is a natural generalization of the well-known dominating set polytope in graphs. In this work we present a complete description of the 2-dominating set polytope of cycles and show that every facet of this polytope can be separated in polynomial time. We use our ndings to derive facets of the 2-dominating set polytope of cacti, i.e. graphs obtained as 1-sum of cycles and edges.