The structure of well-covered graphs with no cycles of length 4 (Q2643318)

Let \(G\) be a finite, simple graph with vertex set \(V(G)\), let \({I}(G)\) be the set of all maximal independent sets in \(G\) and let \(\alpha(G)=\max\{| I| :I \in {I}(G)\}\) denote the independence number of \(G\). Call \(G\) well-covered if \(| I| =\alpha(G)\) for each \(I \in {I}(G)\). Also let \(f:V(G) \rightarrow \mathbb R\) be a weighting of \(G\) which itself is well-covered if there is some value \(K\) such that \(\sum_{x \in M} f(x) = K\) for each \(M \in {I}(G)\). This paper studies the class WC\((\widehat{C_{4}})\) of well-covered graphs with no cycles of length 4. The main result is that if \(G \in \text{WC}(\widehat{C_{4}})\) then \(V(G)\) can be partitioned, using an equivalence relation, into subsets \(V_{1}, \dots, V_{k}\) such that (i) each induced subgraph \(G[V_{i}]\) is well-covered, (ii) \(\sum_{i=1}^{k} \alpha(G[V_{i}]) = \alpha(G)\), and (iii) the vector space of the well-covered weightings of \(G\) is the direct sum of the vector spaces of the well-covered weightings of the \(G[V_{i}]\), each of which has dimension 1. The second result is that the problem of determining whether an edge of a graph is incident with two vertices in the same equivalence class is NP-complete. The authors give a forbidden co-stable subgraph characterization of graphs in WC\((\widehat{C_{4}})\). Finally, they prove that graphs in WC\((\widehat{C_{4}})\) of bounded maximum generalized degree can be recognized in polynomial time.