Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userRegular Turan numbers of complete bipartite graphs
160
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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!$.
rate research
Read More
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 integers $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}})$ $bigg($ 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 wherein 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$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
