Geodesic
Planar graphs with the maximum number of induced 6-cycles
Michael Savery1
1University of Oxford
The electronic journal of combinatorics, Tome 30 (2023) no. 4
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

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.
DOI : 10.37236/11944
Classification : 05C10, 05C30, 05C35, 05C38
Mots-clés : flap-number, \(n\)-vertex planar graphs

Michael Savery  1

1 University of Oxford 
@article{10_37236_11944,
     author = {Michael Savery},
     title = {Planar graphs with the maximum number of induced 6-cycles},
     journal = {The electronic journal of combinatorics},
     year = {2023},
     volume = {30},
     number = {4},
     doi = {10.37236/11944},
     zbl = {1532.05051},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/11944/}
}
TY  - JOUR
AU  - Michael Savery
TI  - Planar graphs with the maximum number of induced 6-cycles
JO  - The electronic journal of combinatorics
PY  - 2023
VL  - 30
IS  - 4
UR  - http://geodesic.mathdoc.fr/articles/10.37236/11944/
DO  - 10.37236/11944
ID  - 10_37236_11944
ER  - 
%0 Journal Article
%A Michael Savery
%T Planar graphs with the maximum number of induced 6-cycles
%J The electronic journal of combinatorics
%D 2023
%V 30
%N 4
%U http://geodesic.mathdoc.fr/articles/10.37236/11944/
%R 10.37236/11944
%F 10_37236_11944
Michael Savery. Planar graphs with the maximum number of induced 6-cycles. The electronic journal of combinatorics, Tome 30 (2023) no. 4. doi: 10.37236/11944

Cité par Sources :