Recognizing Relating Edges in Graphs Without Cycles of Length 6

Abstract A graph G is well-covered if all its maximal independent sets are of the same cardinality. Let $$w:V(G) \longrightarrow \mathbb {R}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>w</mml:mi> <mml:mo>:</mml:mo> <mml:mi>V</mml:mi> <mml:mo>(</mml:mo> <mml:mi>G</mml:mi> <mml:mo>)</mml:mo> <mml:mo>⟶</mml:mo> <mml:mi>R</mml:mi> </mml:mrow> </mml:math> 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)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>x</mml:mi> <mml:mi>y</mml:mi> <mml:mo>∈</mml:mo> <mml:mi>E</mml:mi> <mml:mo>(</mml:mo> <mml:mi>G</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> is relating if there exists $$S \subseteq V(G)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>S</mml:mi> <mml:mo>⊆</mml:mo> <mml:mi>V</mml:mi> <mml:mo>(</mml:mo> <mml:mi>G</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> such that both $$S \cup \{x\}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>S</mml:mi> <mml:mo>∪</mml:mo> <mml:mo>{</mml:mo> <mml:mi>x</mml:mi> <mml:mo>}</mml:mo> </mml:mrow> </mml:math> and $$S \cup \{y\}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>S</mml:mi> <mml:mo>∪</mml:mo> <mml:mo>{</mml:mo> <mml:mi>y</mml:mi> <mml:mo>}</mml:mo> </mml:mrow> </mml:math> are maximal independent sets. If xy is relating then $$ w(x)=w(y)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>w</mml:mi> <mml:mo>(</mml:mo> <mml:mi>x</mml:mi> <mml:mo>)</mml:mo> <mml:mo>=</mml:mo> <mml:mi>w</mml:mi> <mml:mo>(</mml:mo> <mml:mi>y</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> 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}}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>W</mml:mi> <mml:mn>2</mml:mn> </mml:msub> </mml:math> if every two pairwise disjoint independent sets in G are included in two pairwise disjoint maximum independent sets. A vertex $$v \in V(G)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>v</mml:mi> <mml:mo>∈</mml:mo> <mml:mi>V</mml:mi> <mml:mo>(</mml:mo> <mml:mi>G</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> is shedding if for every independent set $$S \subseteq V(G) \setminus N[v]$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>S</mml:mi> <mml:mo>⊆</mml:mo> <mml:mi>V</mml:mi> <mml:mo>(</mml:mo> <mml:mi>G</mml:mi> <mml:mo>)</mml:mo> <mml:mo>\</mml:mo> <mml:mi>N</mml:mi> <mml:mo>[</mml:mo> <mml:mi>v</mml:mi> <mml:mo>]</mml:mo> </mml:mrow> </mml:math> there exists $$u \in N(v)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>u</mml:mi> <mml:mo>∈</mml:mo> <mml:mi>N</mml:mi> <mml:mo>(</mml:mo> <mml:mi>v</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> such that $$S \cup \{u\}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>S</mml:mi> <mml:mo>∪</mml:mo> <mml:mo>{</mml:mo> <mml:mi>u</mml:mi> <mml:mo>}</mml:mo> </mml:mrow> </mml:math> is independent. Shedding vertices play an important role in studying the class $$\mathbf {W_{2}}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>W</mml:mi> <mml:mn>2</mml:mn> </mml:msub> </mml:math> . Recognizing shedding vertices is co- NP- complete. We prove that this problem is co- NP- complete even for graphs without cycles of length 6.