اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدRegular Turan numbers of complete bipartite graphs
160
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
Let $mathrm{rex}(n, F)$ denote the maximum number of edges in an $n$-vertex graph that is regular and does not contain $F$ as a subgraph. We give lower bounds on $mathrm{rex}(n, F)$, that are best possible up to a constant factor, when $F$ is one of $C_4$, $K_{2,t}$, $K_{3,3}$ or $K_{s,t}$ when $t>s!$.
قيم البحث
اقرأ أيضاً
Total dominator total coloring of a graph is a total coloring of the graph such that each object of the graph is adjacent or incident to every object of some color class. The minimum namber of the color classes of a total dominator total coloring of
a graph is called the total dominator total chromatic number of the graph. Here, we will find the total dominator chromatic numbers of wheels, complete bipartite graphs and complete graphs.
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 the bipartite Turan number $ex(m,n,H)$ of a graph $H$ be the maximum number of edges in an $H$-free bipartite graph with two parts of sizes $m$ and $n$, respectively. In this paper, we prove that $ex(m,n,C_{2t})=(t-1)n+m-t+1$ for any positive int
egers $m,n,t$ with $ngeq mgeq tgeq frac{m}{2}+1$. This confirms the rest of a conjecture of Gy{o}ri cite{G97} (in a stronger form), and improves the upper bound of $ex(m,n,C_{2t})$ obtained by Jiang and Ma cite{JM18} for this range. We also prove a tight edge condition for consecutive even cycles in bipartite graphs, which settles a conjecture in cite{A09}. As a main tool, for a longest cycle $C$ in a bipartite graph, we obtain an estimate on the upper bound of the number of edges which are incident to at most one vertex in $C$. Our two results generalize or sharpen a classical theorem due to Jackson cite{J85} in different ways.
We call a $4$-cycle in $K_{n_{1}, n_{2}, n_{3}}$ multipartite, denoted by $C_{4}^{text{multi}}$, if it contains at least one vertex in each part of $K_{n_{1}, n_{2}, n_{3}}$. The Turan number $text{ex}(K_{n_{1},n_{2},n_{3}}, C_{4}^{text{multi}})$ $bi
gg($ respectively, $text{ex}(K_{n_{1},n_{2},n_{3}},{C_{3}, C_{4}^{text{multi}}})$ $bigg)$ is the maximum number of edges in a graph $Gsubseteq K_{n_{1},n_{2},n_{3}}$ such that $G$ contains no $C_{4}^{text{multi}}$ $bigg($ respectively, $G$ contains neither $C_{3}$ nor $C_{4}^{text{multi}}$ $bigg)$. We call a $C^{multi}_4$ rainbow if all four edges of it have different colors. The ant-Ramsey number $text{ar}(K_{n_{1},n_{2},n_{3}}, C_{4}^{text{multi}})$ is the maximum number of colors in an edge-colored of $K_{n_{1},n_{2},n_{3}}$ with no rainbow $C_{4}^{text{multi}}$. In this paper, we determine that $text{ex}(K_{n_{1},n_{2},n_{3}}, C_{4}^{text{multi}})=n_{1}n_{2}+2n_{3}$ and $text{ar}(K_{n_{1},n_{2},n_{3}}, C_{4}^{text{multi}})=text{ex}(K_{n_{1},n_{2},n_{3}}, {C_{3}, C_{4}^{text{multi}}})+1=n_{1}n_{2}+n_{3}+1,$ where $n_{1}ge n_{2}ge n_{3}ge 1.$
For given graphs $G$ and $F$, the Turan number $ex(G,F)$ is defined to be the maximum number of edges in an $F$-free subgraph of $G$. Foucaud, Krivelevich and Perarnau and later independently Briggs and Cox introduced a dual version of this problem w
herein for a given number $k$, one maximizes the number of edges in a host graph $G$ for which $ex(G,H) < k$. Addressing a problem of Briggs and Cox, we determine the asymptotic value of the inverse Turan number of the paths of length $4$ and $5$ and provide an improved lower bound for all paths of even length. Moreover, we obtain bounds on the inverse Turan number of even cycles giving improved bounds on the leading coefficient in the case of $C_4$. Finally, we give multiple conjectures concerning the asymptotic value of the inverse Turan number of $C_4$ and $P_{ell}$, suggesting that in the latter problem the asymptotic behavior depends heavily on the parity of $ell$.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
