# Planar graphs with the maximum number of induced 4-cycles or 5-cycles

@inproceedings{Savery2021PlanarGW, title={Planar graphs with the maximum number of induced 4-cycles or 5-cycles}, author={Michael Savery}, year={2021} }

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.

#### 2 Citations

Planar graphs with the maximum number of induced 6-cycles

- Mathematics
- 2021

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… Expand

The maximum number of induced $C_5$'s in a planar graph

- Mathematics
- 2020

Finding the maximum number of induced cycles of length $k$ in a graph on $n$ vertices has been one of the most intriguing open problems of Extremal Graph Theory. Recently Balogh, Hu, Lidický and… Expand

#### References

SHOWING 1-10 OF 23 REFERENCES

Homomorphism counts in robustly sparse graphs

- Mathematics
- 2021

For a fixed graph $H$ and for arbitrarily large host graphs $G$, the number of homomorphisms from $H$ to $G$ and the number of subgraphs isomorphic to $H$ contained in $G$ have been extensively… Expand

The maximum number of induced $C_5$'s in a planar graph

- Mathematics
- 2020

Finding the maximum number of induced cycles of length $k$ in a graph on $n$ vertices has been one of the most intriguing open problems of Extremal Graph Theory. Recently Balogh, Hu, Lidický and… Expand

Counting paths, cycles and blow-ups in planar graphs

- Mathematics
- 2021

For a planar graph H , let NP(n,H) denote the maximum number of copies of H in an n-vertex planar graph. In this paper, we prove that NP(n, P7) ∼ 4 27n4, NP(n,C6) ∼ (n/3), NP(n,C8) ∼ (n/4) and… Expand

The maximum number of 10- and 12-cycles in a planar graph

- Mathematics
- 2021

For a fixed planar graph H , let NP(n,H) denote the maximum number of copies of H in an n-vertex planar graph. In the case when H is a cycle, the asymptotic value of NP(n,Cm) is currently known for m… Expand

The maximum number of paths of length four in a planar graph

- Mathematics, Computer Science
- Discret. Math.
- 2021

The asymptotic value of f(n, P5), the maximum number of copies of H in an n-vertex planar graph, is determined and conjectures for longer paths are given. Expand

Generalized Planar Turán Numbers

- Mathematics
- 2020

In a generalized Turan problem, we are given graphs $H$ and $F$ and seek to maximize the number of copies of $H$ in an $F$-free graph of order $n$. We consider generalized Turan problems where the… Expand

Subgraph densities in a surface

- Mathematics, Computer Science
- ArXiv
- 2020

This work shows that the answer to the maximum number of copies of H in an n-vertex graph G that embeds in $\Sigma$ is $\Theta(n^{f(H)})$, where f is a graph invariant called the `flap-number' of H, which is independent of $Sigma$. Expand

A bound on the inducibility of cycles

- Mathematics, Computer Science
- J. Comb. Theory, Ser. A
- 2019

It is proved that every n -vertex graph has at most 2 n k / k k induced cycles of length k . Expand

On the exact maximum induced density of almost all graphs and their inducibility

- Mathematics, Computer Science
- J. Comb. Theory, Ser. B
- 2019

It is proved, in particular, that a random graph on $h$ vertices satisfies ${\cal P}_h$ with probability $1-o_h(1)$. Expand

The Maximum Number of Paths of Length Three in a Planar Graph

- Mathematics
- 2019

Let $f(n,H)$ denote the maximum number of copies of $H$ in an $n$-vertex planar graph. The order of magnitude of $f(n,P_k)$, where $P_k$ is a path of length $k$, is… Expand