Remote Access Bulletin of the American Mathematical Society

Bulletin of the American Mathematical Society

ISSN 1088-9485(online) ISSN 0273-0979(print)



A new series of dense graphs of high girth

Authors: F. Lazebnik, V. A. Ustimenko and A. J. Woldar
Journal: Bull. Amer. Math. Soc. 32 (1995), 73-79
MSC: Primary 05C35
MathSciNet review: 1284775
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Let $ k \geq 1$ be an odd integer, $ {t = \left\lfloor {\tfrac{{k + 2}}{4}} \right\rfloor}$, and q be a prime power. We construct a bipartite, q-regular, edge-transitive graph $ CD(k,q)$ of order $ \upsilon \leq 2{q^{k - t + 1}}$ and girth $ g \geq k + 5$. If e is the the number of edges of $ CD(k,q)$, then $ e = \Omega ({{\upsilon ^{1 + \frac{1}{{k - t + 1}}}}})$. These graphs provide the best known asymptotic lower bound for the greatest number of edges in graphs of order $ \upsilon $ and girth at least g, $ g \geq 5$, $ g \ne 11$, 12. For $ g \geq 24$, this represents a slight improvement on bounds established by Margulis and Lubotzky, Phillips, Sarnak; for $ 5 \leq g \leq 23$, $ g \ne 11$, 12, it improves on or ties existing bounds.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Bulletin of the American Mathematical Society with MSC: 05C35

Retrieve articles in all journals with MSC: 05C35

Additional Information

Article copyright: © Copyright 1995 American Mathematical Society

American Mathematical Society