Recognizing relating edges in graphs without cycles of length 6
A graph \(G\) is called well-covered if all its maximal independent sets are of the same cardinality. Let \(w : V(G)\rightarrow \mathbb{R}\) be a weight function. Then \(G\) is called \(w\)-well-covered if all its maximal independent sets are of the same weight. An edge \(xy \in E(G)\) is relating if there exists \(S \subseteq V(G)\) such that both \(S \cup \{x\}\) and \(S \cup \{y\}\) are maximal independent sets. If \(xy\) is relating then \(w(x) = w(y)\) for every weight function \(w\) such that \(G\) is \(w\)-well-covered. Relating edges are of crucial importance for investigating \(w\)-well-covered graphs. The problem of whether an edge is relating is NP-complete. The authors prove that this problem remains NP-complete even for graphs without cycles of length 6. A graph \(G\) is said to belong to the class \(W_2\) if every two pairwise disjoint independent sets in \(G\) are included in two pairwise disjoint maximum independent sets. A vertex \(v \in V(G)\) is called shedding if for every independent set \(S \subseteq V(G) \backslash N[v]\) there exists \(u \in N(v)\) such that \(S\cup \{u\}\) is independent. Shedding vertices play an important role in studying the class \(W_2\), and recognizing shedding vertices is co-NP-complete. It was proved that this problem is co-NP-complete even for graphs without cycles of length 6. A conjecture concludes the paper.
- 1-well-covered graphs revisited
- W₂-graphs and shedding vertices
- A characterization of well covered graphs of girth 5 or greater
- Beyond recognizing well-covered graphs
- Complexity results for generating subgraphs
- Complexity results for well‐covered graphs
- scientific article; zbMATH DE number 434906 (Why is no real title available?)
- Local Structure When All Maximal Independent Sets Have Equal Weight
- On relating edges in graphs without cycles of length 4
- On some subclasses of well-covered graphs
- Recognizing \(\text{W}_2\) graphs
- Recognizing generating subgraphs in graphs without cycles of lengths 6 and 7
- The structure of well-covered graphs with no cycles of length 4
- Three remarks on \(\mathbf{W}_{\mathbf{2}}\) graphs
- Vertex decomposable graphs and obstructions to shellability
- Well-covered graphs without cycles of lengths 4, 5 and 6
This page was built for publication: Recognizing relating edges in graphs without cycles of length 6
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6964823)
