A Characterization of Fractionally Well-Covered Graphs

Abstract

A graph is called well-covered if every maximal independent set has the same size. One generalization of independent sets in graphs is that of a fractional cover -- attach nonnegative weights to the vertices and require that for every vertex the sum of all the weights in its closed neighbourhood be at least 1. In this paper we consider and characterize fractionally well-covered graphs.