Girth of sparse graphs
Abstract
For each fixed k ≥ 0, we give an upper bound for the girth of a graph of order n and size n + k. This bound is likely to be essentially best possible as n → ∞. © 2002 Wiley Periodicals, Inc. J Graph Theory 39: 194–200, 2002; DOI 10.1002/jgt.10023
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Jan 24, 2002
- Source ID
- 10.1002/jgt.10023
Entities
People
- Béla Bollobás
- Endre Szemerédi
Organizations
- Defense Advanced Research Projects Agency
- National Science Foundation