On Relating Edges in Graphs without Cycles of Length 4

Details On Relating Edges in Graphs without Cycles of Length 4 On Relating Edges in Graphs without Cycles of Length 4

2009-08-27

arxiv.org/abs/0908.4016v1

Computer Science

Discrete Mathematics

6 pages, 1 figure

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

On Relating Edges in Graphs without Cycles of Length 4 does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On Relating Edges in Graphs without Cycles of Length 4, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Relating Edges in Graphs without Cycles of Length 4 will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-411737