On Hilbert bases of cuts

A Hilbert basis   is a set of vectors X⊆RdX⊆Rd such that the integer cone (semigroup) generated by XX is the intersection of the lattice generated by XX with the cone generated by XX. Let ℋℋ be the class of graphs whose set of cuts is a Hilbert basis in RERE (regarded as {0,1}{0,1}-characteristic vectors indexed by edges). We show that ℋℋ is not closed under edge deletions, subdivisions, nor 2-sums. Furthermore, no graph having K6∖eK6∖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 K5⊥-minor-free graphs are in ℋℋ, where K5⊥ is the unique 3-connected graph obtained by uncontracting an edge of K5K5. We also establish a relationship between edge deletion and subdivision. Namely, if G′G′ is obtained from G∈ℋG∈ℋ by subdividing ee two or more times, then G∖e∈ℋG∖e∈ℋ if and only if G′∈ℋG′∈ℋ.