On Hilbert bases of cuts
On Hilbert bases of cuts
复制标题
希尔伯特削减基础
DOI：
10.1016/j.disc.2015.09.021
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Tanmay Deshpande
中科院分区：
文献类型：
--
作者：
Luis A. Goddyn;T. Huynh;Tanmay Deshpande
希尔伯特基是向量X⊥R d的集合，使得X生成的整数锥（半群）是X生成的格与X生成的锥的交集。设h为图的切集是R E中的希尔伯特基（设为{0,1}-特征向量以边为索引）的一类图。我们证明了h在边删除、细分或2和下不闭合。此外，没有K 6−e为子图属于h。这纠正了Laurent（1996）中的一个错误。对于正结果，我们给出了两个图的2和产生一个h的成员的条件。使用这些条件，我们证明了所有k5⊥是在h域中的，其中k5⊥是通过取消k5的一条边得到的唯一的3连通图。我们还建立了边缘删除和细分之间的关系。也就是说，如果G ‘是由G∈h除以e两次或两次以上得到的，那么G∈e∈h当且仅当G ’∈h。
A Hilbert basis is a set of vectors X⊆ R 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′∈ ℋ.