Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userExtremal $H$-free planar graphs
95
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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 number} (MC-number for short) of $G$, denoted by $mc(G)$, is the maximum number of colors that ensure $G$ has a monochromatic connection coloring by using this number of colors. This concept was introduced by Caro and Yuster in 2011. They proved that $mc(G)leq m-n+k$ if $G$ is not a $k$-connected graph. In this paper we depict all graphs with $mc(G)=m-n+k+1$ and $mc(G)= m-n+k$ if $G$ is a $k$-connected but not $(k+1)$-connected graph. We also prove that $mc(G)leq m-n+4$ if $G$ is a planar graph, and classify all planar graphs by their monochromatic connectivity numbers.
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-1)-partite graph H whose smallest part has t vertices, and any fixed c>0, there exists a constant C such that whenever G is an n-vertex graph with minimum degree at least ((3r-4)/(3r-1)+c)n, either G contains H, or we can delete at most Cn^(2-1/t) edges from G to yield an r-partite graph.
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, the minimum of second-smallest eigenvalues of Laplacian matrices and hence the maximum of Laplacian spreads among all simple connected graphs of fixed order, minimum degree, maximum degree, minimum size of common neighbors of two adjacent vertices and minimum size of common neighbors of two nonadjacent vertices. Some other extremal graphs are also provided.
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 Paths problem for $H$-free graphs. If $k$ is fixed, we obtain the $k$-Disjoint Paths problem, which is known to be polynomial-time solvable on the class of all graphs for every $k geq 1$. The latter does no longer hold if we need to connect vertices from terminal sets instead of terminal pairs. We completely classify the complexity of $k$-Disjoint Connected Subgraphs for $H$-free graphs, and give the same almost-complete classification for Disjoint Connected Subgraphs for $H$-free graphs as for Disjoint Paths.
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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
