Thumbnail - Request a copy

On perfectly two-edge connected graphs

Mahjoub, Ali Ridha (1997), On perfectly two-edge connected graphs, Discrete Mathematics, 170, 1-3, p. 153-172. http://dx.doi.org/10.1016/S0012-365X(96)00004-0

Type
Article accepté pour publication ou publié
Date
1997
Journal name
Discrete Mathematics
Volume
170
Number
1-3
Publisher
Elsevier
Pages
153-172
Publication identifier
Metadata
Show full item record
Author(s)
Mahjoub, Ali Ridha
Abstract (EN)
This paper studies the graphs for which the 2-edge connected spanning subgraph polytope is completely described by the trivial inequalities and the so-called cut inequalities. These graphs are called perfectly 2-edge connected. The class of perfectly 2-edge connected graphs contains for instance the class of series-parallel graphs. We introduce a new class of perfectly 2-edge connected graphs. We discuss some structural properties of graphs which are (minimally with respect to some reduction operations) nonperfectly 2-edge connected. Using this we give sufficient conditions for a graph to be perfectly 2-edge connected.
Subjects / Keywords
separation problem; Polytopes; 2-edge connected graphs