Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2021
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2110.07319 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866913201122181120 |
|---|---|
| author | Savery, Michael |
| author_facet | Savery, Michael |
| contents | For large $n$ we determine the maximum number of induced 6-cycles which can be contained in a planar graph on $n$ vertices, and we classify the graphs which achieve this maximum. In particular we show that the maximum is achieved by the graph obtained by blowing up three pairwise non-adjacent vertices in a 6-cycle to sets of as even size as possible, and that every extremal example closely resembles this graph. This extends previous work by the author which solves the problem for 4-cycles and 5-cycles. The 5-cycle problem was also solved independently by Ghosh, Győri, Janzer, Paulos, Salia, and Zamora. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2110_07319 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | Planar graphs with the maximum number of induced 6-cycles Savery, Michael Combinatorics For large $n$ we determine the maximum number of induced 6-cycles which can be contained in a planar graph on $n$ vertices, and we classify the graphs which achieve this maximum. In particular we show that the maximum is achieved by the graph obtained by blowing up three pairwise non-adjacent vertices in a 6-cycle to sets of as even size as possible, and that every extremal example closely resembles this graph. This extends previous work by the author which solves the problem for 4-cycles and 5-cycles. The 5-cycle problem was also solved independently by Ghosh, Győri, Janzer, Paulos, Salia, and Zamora. |
| title | Planar graphs with the maximum number of induced 6-cycles |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2110.07319 |