Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn Turan Number for Generalized Theta Graph
101
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
For a graph $H$ consisting of finitely many internally disjoint paths connecting two vertices, with possibly distinct lengths, we estimate the corresponding extremal number $text{ex}(n,H)$. When the lengths of all paths have the same parity, $text{ex}(n,H)$ is $O(n^{1+1/k^ast})$, where $2k^ast$ is the size of the smallest cycle which is included in $H$ as a subgraph. We also establish the matching lower bound in the particular case of $text{ex}(n,Theta_{3,5,5})$, where $Theta_{3,5,5}$ is the graph consisting of three disjoint paths of lengths $3,5$ and $5$ connecting two vertices.
rate research
Read More
The theta graph $Theta_{ell,t}$ consists of two vertices joined by $t$ vertex-disjoint paths of length $ell$ each. For fixed odd $ell$ and large $t$, we show that the largest graph not containing $Theta_{ell,t}$ has at most $c_{ell} t^{1-1/ell}n^{1+1/ell}$ edges and that this is tight apart from the value of $c_{ell}$.
Let $F$ be a fixed graph. The rainbow Turan number of $F$ is defined as the maximum number of edges in a graph on $n$ vertices that has a proper edge-coloring with no rainbow copy of $F$ (where a rainbow copy of $F$ means a copy of $F$ all of whose edges have different colours). The systematic study of such problems was initiated by Keevash, Mubayi, Sudakov and Verstraete. In this paper, we show that the rainbow Turan number of a path with $k+1$ edges is less than $left(frac{9k}{7}+2right) n$, improving an earlier estimate of Johnston, Palmer and Sarkar.
The Turan number of a graph $H$, denoted by $ex(n,H)$, is the maximum number of edges in any graph on $n$ vertices which does not contain $H$ as a subgraph. Let $P_{k}$ denote the path on $k$ vertices and let $mP_{k}$ denote $m$ disjoint copies of $P_{k}$. Bushaw and Kettle [Tur{a}n numbers of multiple paths and equibipartite forests, Combin. Probab. Comput. 20(2011) 837--853] determined the exact value of $ex(n,kP_ell)$ for large values of $n$. Yuan and Zhang [The Tur{a}n number of disjoint copies of paths, Discrete Math. 340(2)(2017) 132--139] completely determined the value of $ex(n,kP_3)$ for all $n$, and also determined $ex(n,F_m)$, where $F_m$ is the disjoint union of $m$ paths containing at most one odd path. They also determined the exact value of $ex(n,P_3cup P_{2ell+1})$ for $ngeq 2ell+4$. Recently, Bielak and Kieliszek [The Tur{a}n number of the graph $2P_5$, Discuss. Math. Graph Theory 36(2016) 683--694], Yuan and Zhang [Tur{a}n numbers for disjoint paths, arXiv: 1611.00981v1] independently determined the exact value of $ex(n,2P_5)$. In this paper, we show that $ex(n,2P_{7})=max{[n,14,7],5n-14}$ for all $n ge 14$, where $[n,14,7]=(5n+91+r(r-6))/2$, $n-13equiv r,(text{mod }6)$ and $0leq r< 6$.
In this paper, we show that, for all $ngeq 5$, the maximum number of $2$-chains in a butterfly-free family in the $n$-dimensional Boolean lattice is $leftlceilfrac{n}{2}rightrceilbinom{n}{lfloor n/2rfloor}$. In addition, for the height-2 poset $K_{s,t}$, we show that, for fixed $s$ and $t$, a $K_{s,t}$-free family in the $n$-dimensional Boolean lattice has $Oleft(nbinom{n}{lfloor n/2rfloor}right)$ $2$-chains.
Let $F$ be a graph. The planar Turan number of $F$, denoted by $text{ex}_{mathcal{P}}(n,F)$, is the maximum number of edges in an $n$-vertex planar graph containing no copy of $F$ as a subgraph. Let $Theta_k$ denote the family of Theta graphs on $kgeq 4$ vertices, that is, a graph obtained by joining a pair of non-consecutive vertices of a $k$-cycle with an edge. Y. Lan, et.al. determined sharp upper bound for $text{ex}_{mathcal{P}}(n,Theta_4)$ and $text{ex}_{mathcal{P}}(n,Theta_5)$. Moreover, they obtained an upper bound for $text{ex}_{mathcal{P}}(n,Theta_6)$. They proved that, $text{ex}_{mathcal{P}}(n,Theta_6)leq frac{18}{7}n-frac{36}{7}$. In this paper, we improve their result by giving a bound which is sharp. In particular, we prove that $text{ex}_{mathcal{P}}(n,Theta_6)leq frac{18}{7}n-frac{48}{7}$ and demonstrate that there are infinitely many $n$ for which there exists a $Theta_6$-free planar graph $G$ on $n$ vertices, which attains the bound.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
