Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userGeneralized Tur{a}n number for linear forests
149
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
The generalized Tur{a}n number $ex(n,K_s,H)$ is defined to be the maximum number of copies of a complete graph $K_s$ in any $H$-free graph on $n$ vertices. Let $F$ be a linear forest consisting of $k$ paths of orders $ell_1,ell_2,...,ell_k$. In this paper, by characterizing the structure of the $F$-free graph with large minimum degree, we determine the value of $ex(n,K_s,F)$ for $n=Omegaleft(|F|^sright)$ and $kgeq 2$ except some $ell_i=3$, and the corresponding extremal graphs. The special case when $s=2$ of our result improves some results of Bushaw and Kettle (2011) and Lidick{y} et al. (2013) on the classical Tur{a}n number for linear forests.
rate research
Read More
Let $mathcal{F}$ be a family of graphs. A graph $G$ is called textit{$mathcal{F}$-free} if for any $Fin mathcal{F}$, there is no subgraph of $G$ isomorphic to $F$. Given a graph $T$ and a family of graphs $mathcal{F}$, the generalized Tur{a}n number of $mathcal{F}$ is the maximum number of copies of $T$ in an $mathcal{F}$-free graph on $n$ vertices, denoted by $ex(n,T,mathcal{F})$. A linear forest is a graph whose connected components are all paths or isolated vertices. Let $mathcal{L}_{n,k}$ be the family of all linear forests of order $n$ with $k$ edges and $K^*_{s,t}$ a graph obtained from $K_{s,t}$ by substituting the part of size $s$ with a clique of the same size. In this paper, we determine the exact values of $ex(n,K_s,mathcal{L}_{n,k})$ and $ex(n,K^*_{s,t},mathcal{L}_{n,k})$. Also, we study the case of this problem when the textit{host graph} is bipartite. Denote by $ex_{bip}(n,T,mathcal{F})$ the maximum possible number of copies of $T$ in an $mathcal{F}$-free bipartite graph with each part of size $n$. We determine the exact value of $ex_{bip}(n,K_{s,t},mathcal{L}_{n,k})$. Our proof is mainly based on the shifting method.
Given a graph $H$ and a positive integer $n,$ the Tur{a}n number of $H$ for the order $n,$ denoted ${rm ex}(n,H),$ is the maximum size of a simple graph of order $n$ not containing $H$ as a subgraph. The book with $p$ pages, denoted $B_p$, is the graph that consists of $p$ triangles sharing a common edge. Bollob{a}s and ErdH{o}s initiated the research on the Tur{a}n number of book graphs in 1975. The two numbers ${rm ex}(p+2,B_p)$ and ${rm ex}(p+3,B_p)$ have been determined by Qiao and Zhan. In this paper we determine the numbers ${rm ex}(p+4,B_p),$ ${rm ex}(p+5,B_p)$ and ${rm ex}(p+6,B_p),$ and characterize the corresponding extremal graphs for the numbers ${rm ex}(n,B_p)$ with $n=p+2,,p+3,,p+4,,p+5.$
For a graph $H$ and a $k$-chromatic graph $F,$ if the Turan graph $T_{k-1}(n)$ has the maximum number of copies of $H$ among all $n$-vertex $F$-free graphs (for $n$ large enough), then $H$ is called $F$-Turan-good, or $k$-Turan-good for short if $F$ is $K_k.$ In this paper, we construct some new classes of $k$-Turan-good graphs and prove that $P_4$ and $P_5$ are $k$-Turan-good for $kge4.$
We consider finite simple graphs. Given a graph $H$ and a positive integer $n,$ the Tur{a}n number of $H$ for the order $n,$ denoted ${rm ex}(n,H),$ is the maximum size of a graph of order $n$ not containing $H$ as a subgraph. ErdH{o}s posed the following problem in 1990: For which graphs $H$ is it true that every graph on $n$ vertices and ${rm ex}(n,H)+1$ edges contains at least two $H$s? Perhaps this is always true. We solve the second part of this problem in the negative by proving that for every integer $kge 4,$ there exists a graph $H$ of order $k$ and at least two orders $n$ such that there exists a graph of order $n$ and size ${rm ex}(n,H)+1$ which contains exactly one copy of $H.$ Denote by $C_4$ the $4$-cycle. We also prove that for every integer $n$ with $6le nle 11,$ there exists a graph of order $n$ and size ${rm ex}(n,C_4)+1$ which contains exactly one copy of $C_4,$ but for $n=12$ or $n=13,$ the minimum number of copies of $C_4$ in a graph of order $n$ and size ${rm ex}(n,C_4)+1$ is $2.$
While the game chromatic number of a forest is known to be at most 4, no simple criteria are known for determining the game chromatic number of a forest. We first state necessary and sufficient conditions for forests with game chromatic number 2 and then investigate the differences between forests with game chromatic number 3 and 4. In doing so, we present a minimal example of a forest with game chromatic number 4, criteria for determining the game chromatic number of a forest without vertices of degree 3, and an example of a forest with maximum degree 3 and game chromatic number 4.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
