On the Independence Number of Triangle Free Graphs with Maximum Degree Three

In this paper, we look at triangle-free graphs with maximum degree three. By an inequality proved by K. Fraughnaugh\(^*\) in 1990, the number of vertices \(v\), edges \(e\), and independence \(i\) of such a graph satisfy \(e \geq \frac{13v}{2} – 14i\). We prove that there is a unique non-cubic, connected graph for which this inequality is sharp. For the cubic case, we describe a computer algorithm that established that two such extremal cubic graphs exist with \(v = 14\), and none for \(v = 28\) or \(42\). We give a complete list of cubic, and provide some new examples of non-cubic, triangle-free graphs with \(v \leq 36\) and independence ratio \(\frac{i}{v}\) less than \(\frac{3}{8}\).