Article ID Journal Published Year Pages File Type
4649148 Discrete Mathematics 2010 6 Pages PDF
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

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,