Critical Independent Sets of a Graph

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)\}$ (Zhang, 1990). Let us recall the following definitions: $\mathrm{core}\left(G\right)$ = $\bigcap$ {S : S is a maximum independent set}. $\mathrm{corona}\left(G\right)$ = $\bigcup$ {S :S is a maximum independent set}. $\ker (G)$ = $\bigcap$ {S : S is a critical independent set}. $\mathrm{diadem}(G)$ = $\bigcup$ {S : S is a critical independent set}. In this paper we present various structural properties of $\ker (G)$, in relation with $\mathrm{core}\left(G\right)$, $\mathrm{corona}\left(G\right)$, and $\mathrm{diadem}(G)$.

15 pages; 12 figures. arXiv admin note: substantial text overlap with arXiv:1102.1138

References in corpus (1)

• Vertices Belonging to All Critical Independent Sets of a Graph