کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4650539 | 1342492 | 2008 | 11 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: On the tightness of the 514 independence ratio On the tightness of the 514 independence ratio](/preview/png/4650539.png)
In 1979, Staton proved that every triangle-free graph GG with maximum degree at most three has an independent set with size at least 514 of the number of vertices of GG. Fraughnaugh [size and independence in triangle-free graphs with maximum degree three, J. Graph Theory 14 (5) (1990) 525–535] and Heckman and Thomas [A new proof of the independence ratio of triangle-free cubic graphs, Discrete Math 233 (2001) 233–237] provided shorter proofs of the same result. An analysis of the cases of equality for the main results in the last paper is presented. Also, a proof that there are only two connected triangle-free graphs with maximum degree at most three and independence ratio 514 is given; it is self-contained and does not require a computer search.
Journal: Discrete Mathematics - Volume 308, Issue 15, 6 August 2008, Pages 3169–3179