اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدOn Turan Number for Generalized Theta Graph
101
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
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.
قيم البحث
اقرأ أيضاً
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 e
dges 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 $kge
q 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.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
