Back to Search Start Over

Exact bipartite Tur\'an numbers of large even cycles

Authors :
Li, Binlong
Ning, Bo
Source :
J. Graph Theory 97 (2021), no. 4, 642--656
Publication Year :
2019

Abstract

Let the bipartite Tur\'an 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 $n\geq m\geq t\geq \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.<br />Comment: Revised version; 16 pages

Subjects

Subjects :
Mathematics - Combinatorics

Details

Database :
arXiv
Journal :
J. Graph Theory 97 (2021), no. 4, 642--656
Publication Type :
Report
Accession number :
edsarx.1901.06137
Document Type :
Working Paper
Full Text :
https://doi.org/10.1002/jgt.22676