On Well-\(k\)-Covered Graphs

O. Favaron1, B. L. Hartnell2
1Université de Paris-Sud, France
2Saint Mary’s University, Canada

Abstract

A set \(S\) of vertices of a graph is \(k\)-independent if each vertex in \(S\) is adjacent to at most \(k-1\) other vertices in \(S\). A graph \(G\) is well-\(k\)-covered if every maximal \(k\)-independent set is maximum. We shall characterize the well-\(k\)-covered trees and for \(k=2\) all such graphs of girth \(8\) or more.