A Class Of Well-Covered Graphs With Girth Four

Abstract

A graph is well-covered if every maximal independent set is also a maximum independent set. A $1$-well-covered graph $G$ has the additional property that $G–v$ is also well-covered for every point $v$ in $G$. Thus, the $1$-well-covered graphs form a subclass of the well-covered graphs. We examine triangle-free $1$-well-covered graphs. Other than $C_5$ and $K_2$, a $1$-well-covered graph must contain a triangle or a $4$-cycle. Thus, the graphs we consider have girth $4$. Two constructions are given which yield infinite families of $1$-well-covered graphs with girth $4$. These families contain graphs with arbitrarily large independence number.