ﻻ يوجد ملخص باللغة العربية
For a planar graph $H$, let $operatorname{mathbf{N}}_{mathcal P}(n,H)$ denote the maximum number of copies of $H$ in an $n$-vertex planar graph. In this paper, we prove that $operatorname{mathbf{N}}_{mathcal P}(n,P_7)sim{4over 27}n^4$, $operatorname{mathbf{N}}_{mathcal P}(n,C_6)sim(n/3)^3$, $operatorname{mathbf{N}}_{mathcal P}(n,C_8)sim(n/4)^4$ and $operatorname{mathbf{N}}_{mathcal P}(n,K_4{1})sim(n/6)^6$, where $K_4{1}$ is the $1$-subdivision of $K_4$. In addition, we obtain significantly improved upper bounds on $operatorname{mathbf{N}}_{mathcal P}(n,P_{2m+1})$ and $operatorname{mathbf{N}}_{mathcal P}(n,C_{2m})$ for $mgeq 4$. For a wide class of graphs $H$, the key technique developed in this paper allows us to bound $operatorname{mathbf{N}}_{mathcal P}(n,H)$ in terms of an optimization problem over weighted graphs.
Hakimi, Schmeichel, and Thomassen in 1979 conjectured that every $4$-connected planar triangulation $G$ on $n$ vertices has at least $2(n-2)(n-4)$ Hamiltonian cycles, with equality if and only if $G$ is a double wheel. In this paper, we show that eve
The problem of maximising the number of cliques among $n$-vertex graphs from various graph classes has received considerable attention. We investigate this problem for the class of $1$-planar graphs where we determine precisely the maximum total numb
In 1930, Kuratowski showed that $K_{3,3}$ and $K_5$ are the only two minor-minimal non-planar graphs. Robertson and Seymour extended finiteness of the set of forbidden minors for any surface. v{S}ir{a}v{n} and Kochol showed that there are infinitely
Let $mathscr{G}$ be the class of plane graphs without triangles normally adjacent to $8^{-}$-cycles, without $4$-cycles normally adjacent to $6^{-}$-cycles, and without normally adjacent $5$-cycles. In this paper, it is showed that every graph in $ma
In 1976, Steinberg conjectured that planar graphs without $4$-cycles and $5$-cycles are $3$-colorable. This conjecture attracted numerous researchers for about 40 years, until it was recently disproved by Cohen-Addad et al. (2017). However, coloring