One-node cutsets and the dominating set polytope
Bouchakour, Mustapha; Mahjoub, Ali Ridha (1997), One-node cutsets and the dominating set polytope, Discrete Mathematics, 165-166, p. 101-123. http://dx.doi.org/10.1016/S0012-365X(96)00164-1
TypeArticle accepté pour publication ou publié
Journal nameDiscrete Mathematics
MetadataShow full item record
Abstract (EN)In this paper we study a composition (decomposition) technique for the dominating set polytope in graphs which are decomposable by one-node cutsets. If G decomposes into G1 and G2, we show that the dominating set polytope of G can be described from two linear systems related to G1 and G2. This gives a way to characterize this polytope for classes of graphs that can be recursively decomposed. This also gives a procedure to describe facets for this polytope. Application of these techniques is discussed for the class of the cactus.
Subjects / KeywordsDominating set polytope; One-node cutset; Composition of polyhedra;
Showing items related by title and author.
Diarrassouba, Ibrahima; Mahjoub, Meriem; Mahjoub, Ali Ridha; Taktak, Raouia (2016) Article accepté pour publication ou publié
Mahjoub, Meriem; Diarrassouba, Ibrahima; Mahjoub, Ali Ridha; Taktak, Raouia (2017) Article accepté pour publication ou publié