## Abstract

A Hilbert basis is a set of vectors X ⊆ ℝ^{d} such that the integer cone (semigroup) generated by X is the intersection of the lattice generated by X with the cone generated by X. Let ℋ be the class of graphs whose set of cuts is a Hilbert basis in R^{E} (regarded as {0,1}-characteristic vectors indexed by edges). We show that ℋ is not closed under edge deletions, subdivisions, nor 2-sums. Furthermore, no graph having K_{6} \ e as a minor belongs to ℋ. This corrects an error in Laurent (1996). For positive results, we give conditions under which the 2-sum of two graphs produces a member of ℋ. Using these conditions we show that all K_{5}^{⊥}-minor-free graphs are in ℋ, where K_{5}^{⊥} is the unique 3-connected graph obtained by uncontracting an edge of K_{5}. We also establish a relationship between edge deletion and subdivision. Namely, if G′ is obtained from G ∈ ℋ by subdividing e two or more times, then G \ e ∈ ℋ if and only if G′ ∈ ℋ.

Original language | English |
---|---|

Pages (from-to) | 721-728 |

Number of pages | 8 |

Journal | Discrete Mathematics |

Volume | 339 |

Issue number | 2 |

DOIs | |

Publication status | Published - 6 Feb 2016 |

Externally published | Yes |

## Keywords

- Combinatorial optimization
- Graph cut
- Hilbert basis