Planar graphs with the maximum number of induced 6-cycles
arXiv:2110.07319 · doi:10.37236/11944
Abstract
For large we determine the maximum number of induced 6-cycles which can be contained in a planar graph on 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.
arXiv comment23 pages, 4 figures; final version; v2: small changes incorporating referee's comments
References in corpus (9)
- Maximum density of an induced 5-cycle is achieved by an iterated blow-up of a 5-cycle
- On the maximum number of cliques in a graph
- A Note on the Inducibility of 4-vertex Graphs
- A bound on the inducibility of cycles
- Subgraph densities in a surface
- The Maximum Number of Pentagons in a Planar Graph
- Homomorphism counts in robustly sparse graphs
- Planar graphs with the maximum number of induced 4-cycles or 5-cycles
- The maximum number of odd cycles in a planar graph