A new series of dense graphs of high girth
Authors:
- F. LazebnikFLF. Lazebnik
- V. A. UstimenkoVUV. A. Ustimenko
- A. J. WoldarAWA. J. Woldar
- 1 January 1995
- journal article
- Published by American Mathematical Society (AMS) in Bulletin of the American Mathematical Society
- Vol. 32 (1) , 73-79
Abstract
Let
be an odd integer,
, and q be a prime power. We construct a bipartite, q -regular, edge-transitive graph
of order
and girth
. If e is the the number of edges of
, then
. These graphs provide the best known asymptotic lower bound for the greatest number of edges in graphs of order
and girth at least g ,
,
, 12. For
, this represents a slight improvement on bounds established by Margulis and Lubotzky, Phillips, Sarnak; for
,
, 12, it improves on or ties existing bounds.
Keywords
This publication has 18 references indexed in Scilit:
- Explicit construction of graphs with an arbitrary large girth and of large sizeDiscrete Applied Mathematics, 1995
- New Examples of Graphs without Small Cycles and of Large SizeEuropean Journal of Combinatorics, 1993
- Constructing random-like graphs1991
- Note on the girth of Ramanujan graphsJournal of Combinatorial Theory, Series B, 1990
- Distance-Regular Graphs1989
- Explicit construction of regular graphs without small cyclesCombinatorica, 1984
- The sextet construction for cubic graphsCombinatorica, 1983
- On a class of degenerate extremal graph problemsCombinatorica, 1983
- Cycles of even length in graphsJournal of Combinatorial Theory, Series B, 1974
- Minimal Regular Graphs of Girths Eight and TwelveCanadian Journal of Mathematics, 1966