On Relating Edges in Graphs without Cycles of Length 4

2009/08/27 by Vadim E. Levit, Levit, Vadim E., David Tankus +1
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Optimization and Search Problems #cs.CC #cs.DM

paper · pdf · doi:10.48550/arxiv.0908.4016

6 pages, 1 figure

arxiv created 2009/08/27 · arxiv updated 2009/12/01

Abstract

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-complete problem to decide whether an edge is relating (Brown, Nowakowski, Zverovich, 2007). We show that the problem remains NP-complete even for graphs without cycles of length 4 and 5. On the other hand, for graphs without cycles of length 4 and 6, the problem can be solved in polynomial time.

Related

• Recognizing Relating Edges in Graphs without Cycles of Length 6
• Graphs with many independent vertex cuts
• Well-Covered Graphs Without Cycles of Lengths 4, 5 and 6
• Maximum Independent Set when excluding an induced minor: K₁ + tK₂ and tC₃ \uplus C₄
• Maximal independent sets in graphs with given matching number