Generating strongly 2-connected digraphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910699207262208 |
|---|---|
| author | Hatzel, Meike Kreutzer, Stephan Protopapas, Evangelos Reich, Florian Stamoulis, Giannos Wiederrecht, Sebastian |
| author_facet | Hatzel, Meike Kreutzer, Stephan Protopapas, Evangelos Reich, Florian Stamoulis, Giannos Wiederrecht, Sebastian |
| contents | We prove that there exist four operations such that given any two strongly $2$-connected digraphs $H$ and $D$ where $H$ is a butterfly-minor of $D$, there exists a sequence $D_0,\dots, D_n$ where $D_0=H$, $D_n=D$ and for every $0\leq i\leq n-1$, $D_i$ is a strongly $2$-connected butterfly-minor of $D_{i+1}$ which is obtained by a single application of one of the four operations.
As a consequence of this theorem, we obtain that every strongly $2$-connected digraph can be generated from a concise family of strongly $2$-connected digraphs by using these four operations. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_09791 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Generating strongly 2-connected digraphs Hatzel, Meike Kreutzer, Stephan Protopapas, Evangelos Reich, Florian Stamoulis, Giannos Wiederrecht, Sebastian Combinatorics 05C20, 05C75 We prove that there exist four operations such that given any two strongly $2$-connected digraphs $H$ and $D$ where $H$ is a butterfly-minor of $D$, there exists a sequence $D_0,\dots, D_n$ where $D_0=H$, $D_n=D$ and for every $0\leq i\leq n-1$, $D_i$ is a strongly $2$-connected butterfly-minor of $D_{i+1}$ which is obtained by a single application of one of the four operations. As a consequence of this theorem, we obtain that every strongly $2$-connected digraph can be generated from a concise family of strongly $2$-connected digraphs by using these four operations. |
| title | Generating strongly 2-connected digraphs |
| topic | Combinatorics 05C20, 05C75 |
| url | https://arxiv.org/abs/2411.09791 |