Symbolic Rees algebras, vertex covers and irreducible representations of Rees cones

Abstract

Let \(G\) be a simple graph and let \(I_c(G)\) be its ideal of vertex covers. We give a graph theoretical description of the irreducible \(b\)-vertex covers of \(G\), i.e., we describe the minimal generators of the symbolic Rees algebra of \(I_c(G)\). Then we study the irreducible \(b\)-vertex covers of the blocker of \(G\), i.e., we study the minimal generators of the symbolic Rees algebra of the edge ideal of \(G\). We give a graph theoretical description of the irreducible binary \(b\)-vertex covers of the blocker of \(G\). It is shown that they correspond to irreducible induced subgraphs of \(G\). As a byproduct we obtain a method, using Hilbert bases, to obtain all irreducible induced subgraphs of \(G\). In particular we obtain all odd holes and antiholes. We study irreducible graphs and give a method to construct irreducible \(b\)-vertex covers of the blocker of \(G\) with high degree relative to the number of vertices of \(G\).