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

Abstract

In this paper, we look at triangle-free graphs with maximum degree three. By an inequality proved by K. Fraughnaugh${}^{\ast }$ in 1990, the number of vertices $v$, edges $e$, and independence $i$ of such a graph satisfy $e\ge \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\le 36$ and independence ratio $\frac{i}{v}$ less than $\frac{3}{8}$.