Details

Autor(en) / Beteiligte

• Savery, Michael

Titel

Planar Graphs with the Maximum Number of Induced 4-Cycles or 5-Cycles

Ist Teil von

• Graphs and combinatorics, 2024-05, Vol.40 (3)

Ort / Verlag

Tokyo: Springer Japan

Erscheinungsjahr

2024

Link zum Volltext

Quelle

SpringerLink

Beschreibungen/Notizen

• For large n we determine exactly the maximum numbers of induced C 4 and C 5 subgraphs that a planar graph on n vertices can contain. We show that K 2 , n - 2 uniquely achieves this maximum in the C 4 case, and we identify the graphs which achieve the maximum in the C 5 case. This extends work in a paper by Hakimi and Schmeichel and a paper by Ghosh, Győri, Janzer, Paulos, Salia, and Zamora which together determine both maxima asymptotically.