Canonical Decompositions of 3-Connected Graphs
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2023
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866911073267875840 |
|---|---|
| author | Carmesin, Johannes Kurkofka, Jan |
| author_facet | Carmesin, Johannes Kurkofka, Jan |
| contents | We offer a new structural basis for the theory of 3-connected graphs, providing a unique decomposition of every such graph into parts that are either quasi 4-connected, wheels, or thickened $K_{3,m}$'s. Our construction is explicit, canonical, and has the following applications: we obtain a new theorem characterising all finite Cayley graphs as either essentially 4-connected, cycles, or complete graphs on at most four vertices, and we provide an automatic proof of Tutte's wheel theorem. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2304_00945 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Canonical Decompositions of 3-Connected Graphs Carmesin, Johannes Kurkofka, Jan Combinatorics Discrete Mathematics 05C40 (Primary), 05C75, 05C83, 05E18 (Secondary) We offer a new structural basis for the theory of 3-connected graphs, providing a unique decomposition of every such graph into parts that are either quasi 4-connected, wheels, or thickened $K_{3,m}$'s. Our construction is explicit, canonical, and has the following applications: we obtain a new theorem characterising all finite Cayley graphs as either essentially 4-connected, cycles, or complete graphs on at most four vertices, and we provide an automatic proof of Tutte's wheel theorem. |
| title | Canonical Decompositions of 3-Connected Graphs |
| topic | Combinatorics Discrete Mathematics 05C40 (Primary), 05C75, 05C83, 05E18 (Secondary) |
| url | https://arxiv.org/abs/2304.00945 |