2024/03/21 by Vadim E. Levit, Levit, Vadim E., David Tankus +1
Computer Science · Engineering · #05C69 #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #G.2.2 #Graph Labeling and Dimension Problems #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2403.14824
openalex publication_date 2024/03/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A graph G is well-covered if all maximal independent sets are of the same cardinality. Let w:V(G) \longrightarrowℝ be a weight function. Then G is w-well-covered if all maximal independent sets are of the same weight. An edge xy ∈ E(G) is relating if there exists an independent set S such that both S ∪ \x\ and S ∪ \y\ are maximal independent sets in the graph. If xy is relating then w(x)=w(y) for every weight function w such that G is w-well-covered. Relating edges play an important role in investigating w-well-covered graphs. The decision problem whether an edge in a graph is relating is NP-complete. We prove that the problem remains NP-complete when the input is restricted to graphs without cycles of length 6. This is an unexpected result because recognizing relating edges is known to be polynomially solvable for graphs without cycles of lengths 4 and 6, graphs without cycles of lengths 5 and 6, and graphs without cycles of lengths 6 and 7. A graph G belongs to the class W2 if every two pairwise disjoint independent sets in G are included in two pairwise disjoint maximum independent sets. It is known that if G belongs to the class W2, then it is well-covered. A vertex v ∈ V(G) is shedding if for every independent set S ⊆ V(G)-N[v], there exists a vertex u ∈ N(v) such that S ∪ \u\ is independent. Shedding vertices play an important role in studying the class W2. Recognizing shedding vertices is co-NP-complete, even when the input is restricted to triangle-free graphs. We prove that the problem is co-NP-complete for graphs without cycles of length 6.