Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
9516212 | Journal of Combinatorial Theory, Series B | 2005 | 10 Pages |
Abstract
The length of the shortest cycle in a graph G is called the girth of G. In particular, we show that if G has girth at least g and average degree at least d, then tw(G)=Ω(1g+1(dâ1)â(gâ1)/2â). In view of a famous conjecture regarding the existence of graphs with girth g, minimum degree δ and having at most c(δâ1)â(gâ1)/2â vertices (for some constant c), this lower bound seems to be almost tight (but for a multiplicative factor of g+1).
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
L.Sunil Chandran, C.R. Subramanian,