Hilbert bases of cuts

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.

Recommendations

Cites work

Cited in

(12)

This page was built for publication: Hilbert bases of cuts

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1916115)