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

DOI:
https://doi.org/10.1090/S0273-0979-1995-00569-0

MathSciNet review:
1284775

Full-text PDF

Abstract | References | Similar Articles | Additional Information

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.

**[1]**C. T. Benson,*Minimal regular graphs of girths eight and twelve*, Canad. J. Math.**18**(1966), 1091-1094. MR**0197342 (33:5507)****[2]**N. L. Biggs,*Graphs with large girth*, Ars Combin.**25-C**(1988), 73-80. MR**943379 (89f:05106)****[3]**N. L. Biggs and A. G. Boshier,*Note on the girth of Ramanujan graphs*, J. Combin. Theory Ser. B**49**(1990), 190-194. MR**1064675 (91g:05133)****[4]**N. L. Biggs and M. J. Hoare,*The sextet construction for cubic graphs*, Combinatorica**3**(1983), 153-165. MR**726453 (85a:05038)****[5]**B. Bollobás,*Extremal graph theory*, Academic Press, London, 1978. MR**506522 (80a:05120)****[6]**J. A. Bondy and M. Simonovits,*Cycles of even length in graphs*, J. Combin. Theory Ser. B**16**(1974), 97-105. MR**0340095 (49:4851)****[7]**A. E. Brouwer, A. M. Cohen, and A. Neumaier,*Distance--regular graphs*, Springer-Verlag, Heidelberg and New York, 1989. MR**1002568 (90e:05001)****[8]**Fan R. K. Chung,*Constructing random-like graphs*, Probabilistic Combinatorics and its Applications, Proc. Sympos. Appl. Math., vol. 44, Amer. Math. Soc., Providence, RI, 1991. MR**1141922 (92m:05169)****[9]**R. J. Faudree and M. Simonovits,*On a class of degenerate extremal graph problems*, Combinatorica**3**(1983), 83-93. MR**716423 (85d:05143)****[10]**Z. Füredi, F. Lazebnik, Á. Seress, V. A. Ustimenko, and A. J. Woldar,*Graphs of prescribed girth and bi-degree*, submitted.**[11]**W. Imrich,*Explicit construction of graphs without small cycles*, Combinatorica**2**(1984), 53-59. MR**739413 (86e:05051)****[12]**F. Lazebnik and V. A. Ustimenko,*New examples of graphs without small cycles and of large size*, Europ. J. Combin.**14**(1993), 445-460. MR**1241911 (94j:05071)****[13]**F. Lazebnik and V. Ustimenko,*Explicit construction of graphs with an arbitrary large girth and of large size*, Discrete Appl. Math. (to appear). MR**1339092 (96e:05088)****[14]**F. Lazebnik, V. A. Ustimenko, and A. J. Woldar,*Properties of certain families of*2*k-cycle free graphs*, J. Combin. Theory Ser. B**60**(1994), 293-298. MR**1271276 (95a:05050)****[15]**-,*A new series of dense graphs of large girth*, Rutcor Research Report RRR 99-93, December 1993.**[16]**A. Lubotzky, R. Phillips, and P. Sarnak,*Ramanujan graphs*, Combinatorica**8**(1988), 261-277. MR**963118 (89m:05099)****[17]**G. A. Margulis,*Explicit construction of graphs without short cycles and low density codes*, Combinatorica**2**(1982), 71-78. MR**671147 (83j:05053)****[18]**-,*Explicit group-theoretical construction of combinatorial schemes and their application to the design of expanders and concentrators*, J. Problems of Inform. Trans.**24**(1988), 39-46; translation from Problemy Peredachi Informatsii**24**(January-March 1988), 51-60. MR**939574 (89f:68054)****[19]**P. Sarnak,*Some applications of modular forms*, Cambridge Tracts in Math., vol. 99, Cambridge Univ. Press, Cambridge, 1990. MR**1102679 (92k:11045)****[20]**M. Simonovits,*Extremal graph theory*, Selected Topics in Graph Theory 2 (L. W. Beineke and R. J. Wilson, eds.), Academic Press, London, 1983, pp. 161-200. MR**797252 (86i:05089)****[21]**V. A. Ustimenko,*Division algebras and Tits geometries*, Dokl. Akad. Nauk USSR**296**(1987), 1061-1065. (Russian) MR**915644 (89f:51030)****[22]**-,*A linear interpretation of the flag geometries of Chevalley groups*, Kiev Univ., Ukrain. Mat. Zh.**42**(March 1990), 383-387. MR**1054885 (91h:20066)****[23]**-,*On the embeddings of some geometries and flag systems in Lie algebras and superalgebras*, Root Systems, Representation and Geometries, IM AN UkrSSR, Kiev, 1990, pp. 3-16. MR**1078874 (92b:17043)****[24]**-,*On some properties of geometries of the Chevalley groups and their generalizations*, Investigation in Algebraic Theory of Combinatorial Objects (I. A. Faradzev, A. A. Ivanov, M. H. Klin, and A. J. Woldar, eds.) Kluwer, Dordrecht, 1991, pp. 112-121.**[25]**V. A. Ustimenko and A. J. Woldar,*An improvement on the Erdös bound for graphs of girth*16, Proceedings of International Conference in Algebra, Barnaul, Russia, September 1991, Contemp. Math., Amer. Math. Soc., Providence, RI (to appear). MR**1332307 (96c:05102)****[26]**A. I. Weiss,*Girth of bipartite sextet graphs*, Combinatorica**4**(1984), 241-245. MR**771732 (86c:05082)****[27]**R. Wenger,*Extremal graphs with no*, , or 's, J. Combin. Theory Ser. B**52**(1991), 113-116. MR**1109426 (92c:05085)****[28]**A. J. Woldar and V. A. Ustimenko,*An application of group theory to extremal graph theory*, Group Theory, Proceedings of the Ohio State-Denison Conference, World Scientific, Singapore, 1993. MR**1348910 (96e:05091)**

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

Retrieve articles in all journals with MSC: 05C35

Additional Information

DOI:
https://doi.org/10.1090/S0273-0979-1995-00569-0

Article copyright:
© Copyright 1995
American Mathematical Society