On dominating set polyhedra of circular interval graphs
From MaRDI portal
Publication:2659194
Abstract: Clique-node and closed neighborhood matrices of circular interval graphs are circular matrices. The stable set polytope and the dominating set polytope on these graphs are therefore closely related to the set packing polytope and the set covering polyhedron on circular matrices. Eisenbrand et al. take advantage of this relationship to propose a complete linear description of the stable set polytope on circular interval graphs. In this paper we follow similar ideas to obtain a complete description of the dominating set polytope on the same class of graphs. As in the packing case, our results are established for a larger class of covering polyhedra of the form Q*(A,b):= conv{x in �^n_+: Ax >= b}, with A a circular matrix and b an integer vector. These results also provide linear descriptions of polyhedra associated with several variantsof the dominating set problem on circular interval graphs.
Recommendations
- On the facets of stable set polytopes of circular interval graphs
- Dominating sets and domatic number of circular arc graphs
- Paired domination on interval and circular-arc graphs
- Constructing dominating sets in circulant graphs
- Parameterized domination in circle graphs
- Parameterized Domination in Circle Graphs
- On the domatic number of interval graphs
- Efficient Algorithms for the Domination Problems on Interval and Circular-Arc Graphs
- scientific article; zbMATH DE number 6120615
- Domination in circulant graphs
Cites work
- Almost all webs are not rank-perfect
- Claw-free graphs. III: Circular interval graphs
- Clique family inequalities for the stable set polytope of quasi-line graphs.
- Cyclic Scheduling via Integer Programs with Circular Ones
- Dominating sets for split and bipartite graphs
- Dominating sets in perfect graphs
- Domination on Cocomparability Graphs
- Domination, independent domination, and duality in strongly chordal graphs
- Edge Dominating Sets in Graphs
- Efficient Algorithms for the Domination Problems on Interval and Circular-Arc Graphs
- Generalized domination and efficient domination in graphs
- Generalized minor inequalities for the set covering polyhedron related to circulant matrices
- scientific article; zbMATH DE number 3159208 (Why is no real title available?)
- scientific article; zbMATH DE number 1302196 (Why is no real title available?)
- scientific article; zbMATH DE number 1095171 (Why is no real title available?)
- scientific article; zbMATH DE number 1102774 (Why is no real title available?)
- Ideal 0, 1 matrices
- Incidence matrices and interval graphs
- Minor related row family inequalities for the set covering polyhedron of circulant matrices
- On packing and covering polyhedra of consecutive ones circulant clutters
- On the dominating set polytope
- On the facial structure of the set covering polytope
- On the set covering polyhedron of circulant matrices
- Row family inequalities for the set covering polyhedron
- Some advances on the set covering polyhedron of circulant matrices
- The minor inequalities in the description of the set covering polyhedron of circulant matrices
- The stable set polytope of quasi-line graphs
- The structure of claw-free graphs
- Variations of \(Y\)-dominating functions on graphs
Cited in
(4)
This page was built for publication: On dominating set polyhedra of circular interval graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2659194)
