On Relating Edges in Graphs without Cycles of Length 4

Vadim E. Levit, David Tankus

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} and S_{y} are both maximal independent sets in G. It is an NP-co…