Advertisement
Published in:
2009 | OriginalPaper | Chapter
On Related Edges in Well-Covered Graphs without Cycles of Length 4 and 6
Authors : Vadim E. Levit, David Tankus
Published in: Graph Theory, Computational Intelligence and Thought
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
A graph is
well-covered
if every maximal independent set has the same cardinality. The recognition problem of well-covered graphs is known to be
co-NPC
. The complexity status of the problem is not known if the input is restricted to graphs with no cycles of length 4. We conjecture that the problem is polynomial if the input graph does not contain cycles of length 4 and 6, and prove several theorems supporting our conjecture.