A graph G is well-covered if all its maximal independent sets are of the same cardinality. Let \(w:V(G) \longrightarrow \mathbb {R}\) be a weight function. Then G is 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 whether an edge is relating is NP-complete. We prove that this problem remains NP-complete even for graphs without cycles of length 6. A graph G belongs to the class \(\mathbf {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 shedding if for every independent set \(S \subseteq V(G) \setminus 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 \(\mathbf {W_{2}}\) . Recognizing shedding vertices is co-NP-complete. We prove that this problem is co-NP-complete even for graphs without cycles of length 6.
