Article ID Journal Published Year Pages File Type
418611 Discrete Applied Mathematics 2011 9 Pages PDF
Abstract

Heckman and Thomas [C.C. Heckman, R. Thomas, A new proof of the independence ratio of triangle-free cubic graphs, Discrete Math. 233 (2001) 233–237] proved that every connected subcubic triangle-free graph GG has an independent set of order at least (4n(G)−m(G)−1)/7(4n(G)−m(G)−1)/7 where n(G)n(G) and m(G)m(G) denote the order and size of GG, respectively. We conjecture that every connected subcubic graph GG of odd girth at least seven has an independent set of order at least (5n(G)−m(G)−1)/9(5n(G)−m(G)−1)/9 and verify our conjecture under some additional technical assumptions.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, , ,