Premium
Girth of sparse graphs
Author(s) -
Bollobás Béla,
Szemerédi Endre
Publication year - 2002
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.10023
Subject(s) - mathematics , combinatorics , girth (graph theory) , upper and lower bounds , graph , odd graph , discrete mathematics , triangle free graph , line graph , graph power , pathwidth , mathematical analysis
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