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 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 K5⊥-minor-free graphs are in ℋ, where K5⊥ 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′ ∈ ℋ.

On Hilbert bases of cuts / Goddyn, L.; Huynh, T.; Deshpande, T.. - In: DISCRETE MATHEMATICS. - ISSN 0012-365X. - 339:2(2016), pp. 721-728. [10.1016/j.disc.2015.09.021]

### On Hilbert bases of cuts

#### 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 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 K5⊥-minor-free graphs are in ℋ, where K5⊥ 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′ ∈ ℋ.
##### Scheda breve Scheda completa
2016
Combinatorial optimization; Graph cut; Hilbert basis
01 Pubblicazione su rivista::01a Articolo in rivista
On Hilbert bases of cuts / Goddyn, L.; Huynh, T.; Deshpande, T.. - In: DISCRETE MATHEMATICS. - ISSN 0012-365X. - 339:2(2016), pp. 721-728. [10.1016/j.disc.2015.09.021]
File allegati a questo prodotto
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: `https://hdl.handle.net/11573/1707606`
##### Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

• ND
• 3
• ND