Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4649148 | Discrete Mathematics | 2010 | 6 Pages |
Abstract
For a non-negative integer TT, we prove that the independence number of a graph G=(V,E)G=(V,E) in which every vertex belongs to at most TT triangles is at least ∑u∈Vf(d(u),T)∑u∈Vf(d(u),T) where d(u)d(u) denotes the degree of a vertex u∈Vu∈V, f(d,T)=1d+1 for T≥d2 and f(d,T)=(1+(d2−d−2T)f(d−1,T))/(d2+1−2T)f(d,T)=(1+(d2−d−2T)f(d−1,T))/(d2+1−2T) for T
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Anett Boßecker, Dieter Rautenbach,