Planar Graphs with the Maximum Number of Induced 4-Cycles or 5-Cycles
For large n we determine exactly the maximum numbers of induced C4 and C5 subgraphs that a planar graph on n vertices can contain. We show that K2, n-2 uniquely achieves this maximum in the C4 case, and we identify the graphs which achieve the maximum in the C5 case. This extends work in a paper by...
| Main Author: | |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
Springer
2024
|
| Summary: | For large n we determine exactly the maximum numbers of induced C4 and C5 subgraphs that a planar graph on n vertices can contain. We show that K2, n-2 uniquely achieves this maximum in the C4 case, and we identify the graphs which achieve the maximum in the C5 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. |
|---|