On Almost Well-Covered Graphs of Girth at Least 6

Abstract

We consider a relaxation of the concept of well-covered graphs, which are graphs with all maximal independent sets of the same size. The extent to which a graph fails to be well-covered can be measured by its independence gap, defined as the difference between the maximum and minimum sizes of a maximal independent set in G. While the well-covered graphs are exactly the graphs of independence gap zero, we investigate in this paper graphs of independence gap one, which we also call almost well-covered graphs. Previous works due to Finbow et al. and Barbosa et al. have implications for the structure of almost well-covered graphs of girth at least k for k is an element of {7, 8}. We focus on almost well-covered graphs of girth at least 6. We show that every graph in this class has at most two vertices each of which is adjacent to exactly 2 leaves. We give efficiently testable characterizations of almost well-covered graphs of girth at least 6 having exactly one or exactly two such vertices. Building on these results, we develop a polynomial-time recognition algorithm of almost well-covered {C-3, C-4, C-5, C-7}-free graphs.