Flow-critical graphs
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866915782313639936 |
|---|---|
| author | Árnadóttir, Arnbjörg Soffía Dvořák, Zdeněk Lidický, Bernard Moore, Benjamin Smith-Roberge, Evelyne Šámal, Robert |
| author_facet | Árnadóttir, Arnbjörg Soffía Dvořák, Zdeněk Lidický, Bernard Moore, Benjamin Smith-Roberge, Evelyne Šámal, Robert |
| contents | Lovász et al. proved that every $6$-edge-connected graph has a nowhere-zero $3$-flow. In fact, they proved a more technical statement which says that there exists a nowhere zero $3$-flow that extends the flow prescribed on the incident edges of a single vertex $z$ with bounded degree. We extend this theorem of Lovász et al. to allow $z$ to have arbitrary degree, but with the additional assumption that there is another vertex $x$ with large degree and no small cut separating $x$ and $z$. Using this theorem, we prove two results regarding the generation of minimal graphs with the property that prescribing the edges incident to a vertex with specific flow does not extend to a nowhere-zero $3$-flow. We use this to further strengthen the theorem of Lovász et al., as well as make progress on a conjecture of Li et al. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_01451 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Flow-critical graphs Árnadóttir, Arnbjörg Soffía Dvořák, Zdeněk Lidický, Bernard Moore, Benjamin Smith-Roberge, Evelyne Šámal, Robert Combinatorics Lovász et al. proved that every $6$-edge-connected graph has a nowhere-zero $3$-flow. In fact, they proved a more technical statement which says that there exists a nowhere zero $3$-flow that extends the flow prescribed on the incident edges of a single vertex $z$ with bounded degree. We extend this theorem of Lovász et al. to allow $z$ to have arbitrary degree, but with the additional assumption that there is another vertex $x$ with large degree and no small cut separating $x$ and $z$. Using this theorem, we prove two results regarding the generation of minimal graphs with the property that prescribing the edges incident to a vertex with specific flow does not extend to a nowhere-zero $3$-flow. We use this to further strengthen the theorem of Lovász et al., as well as make progress on a conjecture of Li et al. |
| title | Flow-critical graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2502.01451 |