Hostname: page-component-74656f9884-8r8nv Total loading time: 0 Render date: 2026-11-07T15:15:53.940Z Has data issue: false hasContentIssue false

A Note on Bipartite Graphs Without 2k-Cycles

Published online by Cambridge University Press:  11 October 2005

ASSAF NAOR
Affiliation:
Microsoft Research, One Microsoft Way, Redmond, WA 98052-6399, USA (e-mail: anaor@microsoft.com)
JACQUES VERSTRAËTE
Affiliation:
Faculty of Mathematics, University of Waterloo, 200 University Avenue West, Waterloo, Canada N2L 3G1 (e-mail: jverstra@math.uwaterloo.ca)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

The question of the maximum number $\mbox{ex}(m,n,C_{2k})$ of edges in an m by n bipartite graph without a cycle of length 2k is addressed in this note. For each $k \geq 2$, it is shown that $\mbox{ex}(m,n,C_{2k}) \leq \begin{cases} (2k-3)\bigl[(mn)^{\frac{k+1}{2k}} + m + n\bigr] & \mbox{ if }k \mbox{ is odd,}\\[2pt] (2k-3)\bigl[m^{\frac{k+2}{2k}}\, n^{\frac{1}{2}} + m + n\bigr] & \mbox{ if }k \mbox{ is even.}\\ \end{cases}$

Information

Type
Paper
Copyright
2005 Cambridge University Press