Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2509.23394 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909959065698304 |
|---|---|
| author | Abrishami, Tara Bowler, Nathan Joó, Attila Reich, Florian Tao, Qiuzhenyu |
| author_facet | Abrishami, Tara Bowler, Nathan Joó, Attila Reich, Florian Tao, Qiuzhenyu |
| contents | Recently, bidirected graphs have received increasing attention from the graph theory community with both structural and algorithmic results. Bidirected graphs are a generalization of directed graphs, consisting of an undirected graph together with a map assigning each endpoint of every edge either sign $+$ or $-$. The connectivity properties of bidirected graphs are more complex than those of directed graphs and not yet well understood. In this paper, we show a structure theorem about rooted connectivity in bidirected graphs in terms of directed graphs. As applications, we prove Lovász' flame theorem, Pym's theorem and a strong variant of Menger's theorem for a class of bidirected graphs and provide counterexamples in the general case. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_23394 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A structure theorem for rooted connectivity in bidirected graphs Abrishami, Tara Bowler, Nathan Joó, Attila Reich, Florian Tao, Qiuzhenyu Combinatorics Recently, bidirected graphs have received increasing attention from the graph theory community with both structural and algorithmic results. Bidirected graphs are a generalization of directed graphs, consisting of an undirected graph together with a map assigning each endpoint of every edge either sign $+$ or $-$. The connectivity properties of bidirected graphs are more complex than those of directed graphs and not yet well understood. In this paper, we show a structure theorem about rooted connectivity in bidirected graphs in terms of directed graphs. As applications, we prove Lovász' flame theorem, Pym's theorem and a strong variant of Menger's theorem for a class of bidirected graphs and provide counterexamples in the general case. |
| title | A structure theorem for rooted connectivity in bidirected graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2509.23394 |