New constructions of bipartite graphs on \(m\), \(n\) vertices with many edges and without small cycles
type: Item
instance of: scholarly article
title: New constructions of bipartite graphs on \(m\), \(n\) vertices with many edges and without small cycles
zbMATH Open document ID: 0797.05055
published in: Journal of Combinatorial Theory. Series B
publication date: 1994-10-10T00:00:00Z
review text: For arbitrary odd prime power \(q\) and \(s\in(0,1]\) such that \(q^ s\) is an integer, we construct a doubly-infinite series of \((q^ 5,q^{3+s})\)-bipartite graphs which are biregular of degrees \(q^ s\) and \(q^ 2\) and of girth 8. These graphs have the greatest number of edges among all known \((n,m)\)-bipartite graphs with the same asymptotics of \(\log_ nm\), \(n\to\infty\). For \(s={1\over 3}\), our graphs provide an explicit counterexample to a conjecture of Erdős which states that an \((n,m)\)-bipartite graph with \(m=O(n^{2/3})\) and girth at least 8 has \(O(n)\) edges. This conjecture was recently disproved by \textit{D. de Caen} and \textit{L. A. Székely} [Colloq. Math. Soc. János Bolyai 60, 135-142 (1992; Zbl 0795.05083)], who established the existence of a family of such graphs having \(n^{1+1/57+o(1)}\) edges. Our graphs have \(n^{1+1/15}\) edges, and so come closer to the best known upper bound of \(O(n^{1+1/9})\).
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 599867
zbMATH Keywords: bipartite graphs
zbMATH Keywords: small cycles
zbMATH Keywords: biregular graph
zbMATH Keywords: conjecture of Erdős
zbMATH Keywords: upper bound
author: Felix Lazebnik
author: V. A. Ustimenko
author: Andrew J. Woldar
MaRDI profile type: Publication
full work available at URL: jctb.1994.1036
OpenAlex ID: W2060200869
DOI: 10.1006/JCTB.1994.1036
description: scientific article; zbMATH DE number 599867