2016/09/22 by Hujdurović, Ademir, Milanič, Martin, Ries, Bernard
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.1609.06961
A graph is said to be well-covered if all its maximal independent sets are of the same size. In 1999, Yamashita and Kameda introduced a subclass of well-covered graphs, called localizable graphs and defined as graphs having a partition of the vertex set into strong cliques, where a clique in a graph is strong if it intersects all maximal independent sets. Yamashita and Kameda observed that all well-covered trees are localizable, pointed out that the converse inclusion fails in general, and asked for a characterization of localizable graphs. In this paper we obtain several structural and algorithmic results about localizable graphs. Our results include a proof of the fact that every very well-covered graph is localizable and characterizations of localizable graphs within the classes of line graphs, triangle-free graphs, C4-free graphs, and cubic graphs, each leading to a polynomial time recognition algorithm. On the negative side, we prove NP-hardness of recognizing localizable graphs within the classes of weakly chordal graphs, complements of line graphs, and graphs of independence number three. Furthermore, using localizable graphs we disprove a conjecture due to Zaare-Nahandi about k-partite well-covered graphs having all maximal cliques of size k. Our results unify and generalize several results from the literature.