A note on bipartite graphs without 2k-cycles

Assaf Naor, Jacques Verstraëte

Research output: Contribution to journalArticle

24 Scopus citations

Abstract

The question of the maximum number ex(m,n,C2k) 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 ex(m,n,C2k) ≤ { (2k-3)[(mn)k+1/2k + m + n] if k is odd,[2pt] (2k-3)[m k+2/2k n1/2 + m + n] if k is even.

Original languageEnglish (US)
Pages (from-to)845-849
Number of pages5
JournalCombinatorics Probability and Computing
Volume14
Issue number5-6
DOIs
StatePublished - Nov 1 2005
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Statistics and Probability
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'A note on bipartite graphs without 2k-cycles'. Together they form a unique fingerprint.

  • Cite this