Thumbnail - Request a copy

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

Type
Article accepté pour publication ou publié
Date
1997
Journal name
Discrete Mathematics
Volume
165-166
Publisher
Elsevier
Pages
101-123
Publication identifier
Metadata
Show full item record
Author(s)
Bouchakour, Mustapha
Mahjoub, Ali Ridha
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 / Keywords
Dominating set polytope; One-node cutset; Composition of polyhedra;