A note on the structure of locally finite planar quasi-transitive graphs
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866912511293390848 |
|---|---|
| author | Giocanti, Ugo |
| author_facet | Giocanti, Ugo |
| contents | In an early work from 1896, Maschke established the complete list of all finite planar Cayley graphs. This result initiated a long line of research over the next century, aiming at characterizing in a similar way all planar infinite Cayley graphs. Droms (2006) proved a structure theorem for finitely generated planar groups, i.e., finitely generated groups admitting a planar Cayley graph, in terms of Bass-Serre decompositions. As a byproduct of his structure theorem, Droms proved that such groups are finitely presented. More recently, Hamann (2018) gave a graph theoretical proof that every planar quasi-transitive graph $G$ admits a generating $\mathrm{Aut}(G)$-invariant set of closed walks with only finitely many orbits, and showed that a consequence is an alternative proof of Droms' result. Based on the work of Hamann, we show in this note that we can also obtain a general structure theorem for $3$-connected locally finite planar quasi-transitive graphs, namely that every such graph admits a canonical tree-decomposition whose edge-separations correspond to cycle-separations in the (unique) embedding of $G$, and in which every part admits a vertex-accumulation free embedding. This result can be seen as a version of Droms' structure theorem for quasi-transitive planar graphs. As a corollary, we obtain an alternative proof of a result of Hamann, Lehner, Miraftab and Rühmann (2022) that every locally finite quasi-transitive planar graph admits a canonical tree-decomposition, whose parts are either $1$-ended or finite planar graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_20300 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A note on the structure of locally finite planar quasi-transitive graphs Giocanti, Ugo Combinatorics Discrete Mathematics 05C10 (Primary), 05C63 (Secondary), 05C75 (Secondary), 68R10 (Secondary) G.2.2 In an early work from 1896, Maschke established the complete list of all finite planar Cayley graphs. This result initiated a long line of research over the next century, aiming at characterizing in a similar way all planar infinite Cayley graphs. Droms (2006) proved a structure theorem for finitely generated planar groups, i.e., finitely generated groups admitting a planar Cayley graph, in terms of Bass-Serre decompositions. As a byproduct of his structure theorem, Droms proved that such groups are finitely presented. More recently, Hamann (2018) gave a graph theoretical proof that every planar quasi-transitive graph $G$ admits a generating $\mathrm{Aut}(G)$-invariant set of closed walks with only finitely many orbits, and showed that a consequence is an alternative proof of Droms' result. Based on the work of Hamann, we show in this note that we can also obtain a general structure theorem for $3$-connected locally finite planar quasi-transitive graphs, namely that every such graph admits a canonical tree-decomposition whose edge-separations correspond to cycle-separations in the (unique) embedding of $G$, and in which every part admits a vertex-accumulation free embedding. This result can be seen as a version of Droms' structure theorem for quasi-transitive planar graphs. As a corollary, we obtain an alternative proof of a result of Hamann, Lehner, Miraftab and Rühmann (2022) that every locally finite quasi-transitive planar graph admits a canonical tree-decomposition, whose parts are either $1$-ended or finite planar graphs. |
| title | A note on the structure of locally finite planar quasi-transitive graphs |
| topic | Combinatorics Discrete Mathematics 05C10 (Primary), 05C63 (Secondary), 05C75 (Secondary), 68R10 (Secondary) G.2.2 |
| url | https://arxiv.org/abs/2412.20300 |