ﻻ يوجد ملخص باللغة العربية
Given a graph $H$, a graph is $H$-free if it does not contain $H$ as a subgraph. We continue to study the topic of extremal planar graphs, that is, how many edges can an $H$-free planar graph on $n$ vertices have? We define $ex_{_mathcal{P}}(n,H)$ to be the maximum number of edges in an $H$-free planar graph on $n $ vertices. We first obtain several sufficient conditions on $H$ which yield $ex_{_mathcal{P}}(n,H)=3n-6$ for all $nge |V(H)|$. We discover that the chromatic number of $H$ does not play a role, as in the celebrated ErdH{o}s-Stone Theorem. We then completely determine $ex_{_mathcal{P}}(n,H)$ when $H$ is a wheel or a star. Finally, we examine the case when $H$ is a $(t, r)$-fan, that is, $H$ is isomorphic to $K_1+tK_{r-1}$, where $tge2$ and $rge 3$ are integers. However, determining $ex_{_mathcal{P}}(n,H)$, when $H$ is a planar subcubic graph, remains wide open.
An edge-coloring of a connected graph $G$ is called a {em monochromatic connection coloring} (MC-coloring for short) if any two vertices of $G$ are connected by a monochromatic path in $G$. For a connected graph $G$, the {em monochromatic connection
By using the Szemeredi Regularity Lemma, Alon and Sudakov recently extended the classical Andrasfai-Erd~os-Sos theorem to cover general graphs. We prove, without using the Regularity Lemma, that the following stronger statement is true. Given any (r-
The Laplacian spread of a graph is the difference between the largest eigenvalue and the second-smallest eigenvalue of the Laplacian matrix of the graph. We find that the class of strongly regular graphs attains the maximum of largest eigenvalues, th
The well-known Disjoint Paths problem is to decide if a graph contains k pairwise disjoint paths, each connecting a different terminal pair from a set of k distinct pairs. We determine, with an exception of two cases, the complexity of the Disjoint P
The Turan problem asks for the largest number of edges in an $n$-vertex graph not containing a fixed forbidden subgraph $F$. We construct a new family of graphs not containing $K_{s,t}$, for $t= C^s$, with $Omega(n^{2-1/s})$ edges matching the upper bound of Kovari, Sos and Turan.