Advertisement
Published in:
2019 | OriginalPaper | Chapter
Critical and Maximum Independent Sets Revisited
Authors : Vadim E. Levit, Eugen Mandrescu
Published in: Mathematical Optimization Theory and Operations Research
Publisher: Springer International Publishing
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
Abstract
Let G be a simple graph with vertex set \(V\left( G\right) \).
A set \(S\subseteq V\left( G\right) \) is independent if no two vertices from S are adjacent, and by \(\mathrm {Ind}(G)\) we mean the family of all independent sets of G.
The number \(d\left( X\right) =\) \(\left| X\right| -\left| N(X)\right| \) is the difference of \(X\subseteq V\left( G\right) \), and a set \(A\in \mathrm {Ind}(G)\) is critical if \(d(A)=\max \{d\left( I\right) :I\in \mathrm {Ind}(G)\}\) [34].
Let us recall the following definitions:
-
\(\mathrm {core}\left( G\right) = {\displaystyle \bigcap } \left\{ S:S\textit{ is a maximum independent set}\right\} \) [16],
-
\(\mathrm {corona}\left( G\right) = {\displaystyle \bigcup } \left\{ S:S\textit{ is a maximum independent set}\right\} \) [5],
-
\(\mathrm {\ker }(G)= {\displaystyle \bigcap } \left\{ S:S\textit{ is a critical independent set}\right\} \) [18],
-
\(\mathrm {nucleus}(G)= {\displaystyle \bigcap } \left\{ S:S\textit{ is a maximum critical independent set}\right\} \) [12]
-
\(\mathrm {diadem}(G)= {\displaystyle \bigcup } \left\{ S:S\textit{ is a (maximum) critical independent set}\right\} \) [24].
In this paper we focus on interconnections between \(\ker \), core, corona, \(\mathrm {nucleus}\), and diadem.