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
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 $ 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?)

  • [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 2k-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 $ {C^4}$, $ {C^6}$, or $ {C^{10}}$'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)

Similar Articles

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

American Mathematical Society