Hilbert bases of cuts
type: Item
instance of: scholarly article
title: Hilbert bases of cuts
zbMATH Open document ID: 0853.05065
DOI: 10.1016/0012-365X(95)00192-Y
author: Monique Laurent
published in: Discrete Mathematics
publication date: 1996-07-02T00:00:00Z
review text: Let \(G = (V,E)\) be a graph with \(E(G) = \{e_1, \dots, e_m\}\). For each edge-cut \(T\) of \(G\), let \(\overline T = (x_1, \dots, x_m)\) be an \(m\)-dimensional vector with \(x_i = 1\) if \(e_i \in T\), and \(x_i = 0\) otherwise. The cone \(R_+ (G)\) of \(G\) is the set consisting of all linear combinations of \(\overline T\) for all edge-cuts \(T\) of \(G\) with positive real coefficients. The lattice \(Z(G)\) of \(G\) is the set consisting of all linear combinations of \(\overline T\) for all edge-cuts \(T\) of \(G\) with integer coefficients. The integer cone \(Z_+ (G)\) of \(G\) is the set consisting of all linear combinations of \(\overline T\) for all edge-cuts \(T\) of \(G\) with positive integer coefficients. It is obvious that, for each graph \(G\), \(Z_+ (G) \subseteq R_+ (G) \cap Z (G)\). Let \({\mathcal H}\) be the class of all graphs satisfying \(Z_+ (G) = R_+ (G) \cap Z(G)\). It is proved that every proper subgraph of \(K_6\) belongs to \({\mathcal H}\) and every graph from \({\mathcal H}\) does not have \(K_6\) as a minor.
Mathematics Subject Classification ID: 05C70
zbMATH DE Number: 896004
zbMATH Keywords: Hilbert bases
zbMATH Keywords: edge-cut
zbMATH Keywords: cone
zbMATH Keywords: minor
MaRDI profile type: Publication
cites work: Graphs with the Circuit Cover Property
cites work: The max-cut problem on graphs not contractible to \(K_ 5\)
cites work: On the cut polytope
cites work: Addresses for graphs
cites work: Une propriété extremale des plans projectifs finis dans une classe de codes équidistants
cites work: Q3336286
cites work: Lattice Points of Cut Cones
cites work: Extension operations for cuts
cites work: Total dual integrality and integer polyhedra
cites work: Q4273860
cites work: The Hilbert basis of the cut cone over the complete graph K 6
cites work: The cocycle lattice of binary matroids
cites work: Q3916595
cites work: Decomposition of regular matroids
cites work: Matroids and multicommodity flows
cites work: Über eine Eigenschaft der ebenen Komplexe
description: scientific article; zbMATH DE number 896004