On relating edges in graphs without cycles of length 4
An edge xy is relating in the graph G if there is an independent set S, containing neither x nor y , such that S?{x} S ? { x } and S?{y} S ? { y } are both maximal independent sets in G. It is an NP-complete problem to decide whether an edge is relating [1]. We show that the problem remains NP-complete even for graphs without cycles of lengths 4 and 5. On the other hand, we show that for graphs without cycles of lengths 4 and 6, the problem can be solved in polynomial time.
relating edge well-covered graph ford and fulkerson algorithm sat problem