
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.
Forbidden co-stable subgraph., Vector space, Independent set, \(C_4\)-free graph, Theoretical Computer Science, Well-covered weighting, independent set, Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.), Well-covered graph, vector space, Discrete Mathematics and Combinatorics, well-covered graph, well-covered weighting, C4-free graph, forbidden co-stable subgraph
Forbidden co-stable subgraph., Vector space, Independent set, \(C_4\)-free graph, Theoretical Computer Science, Well-covered weighting, independent set, Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.), Well-covered graph, vector space, Discrete Mathematics and Combinatorics, well-covered graph, well-covered weighting, C4-free graph, forbidden co-stable subgraph
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 19 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
