A Hilbert basis is a set of vectors X⊆Rd such that the integer cone (semigroup) generated by 160c54792ab6bb0354" title="Click to view the MathML source">X is the intersection of the lattice generated by 160c54792ab6bb0354" title="Click to view the MathML source">X with the cone generated by 160c54792ab6bb0354" title="Click to view the MathML source">X. Let ℋ be the class of graphs whose set of cuts is a Hilbert basis in RE (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 K6∖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 -minor-free graphs are in ℋ, where is the unique 3-connected graph obtained by uncontracting an edge of K5. 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′∈ℋ.