Symbolic Rees algebras, vertex covers and irreducible representations of Rees cones
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 cover...
Saved in:
| Date: | 2018 |
|---|---|
| Main Authors: | , |
| Format: | Article |
| Language: | English |
| Published: |
Lugansk National Taras Shevchenko University
2018
|
| Subjects: | |
| Online Access: | https://admjournal.luguniv.edu.ua/index.php/adm/article/view/651 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Algebra and Discrete Mathematics |
Institution
Algebra and Discrete Mathematics| Summary: | 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\). |
|---|