2003 | OriginalPaper | Chapter
The Complexity of Some Problems on Maximal Independent Sets in Graphs
Authors : Igor Zverovich, Yury Orlovich
Published in: Operations Research Proceedings 2002
Publisher: Springer Berlin Heidelberg
Included in: Professional Book Archive
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
Let mi(G) be the number of maximal independent sets in a graph G. A graph G is mi-minimal if mi(H) < mi(G) for each proper induced subgraph H of G. As it is shown in [6], every graph G without duplicated or isolated vertices has at most 2k-1 +k - 2 vertices, where k = mi(G) > 2. Hence the extremal problem of calculating m(k) = max{IV(G)1: G is a mi-minimal graph with mi(G) = k} has a solution for any k ~ 1 We show that 2(k -1) ~ m(k) ~ k(k -1) for any k ~ andconjecture that m(k) = 2(k - 1). We also prove NP-completeness of some related problems.