On the structure of the minimum critical independent set of a graph (Q1939576): Difference between revisions

A subset of vertices \(S\) of a graph \(G=(V,E)\) is independent if no two vertices of \(S\) are adjacent. An independent set is critical, if the difference between its cardinality and the cardinality of its neighborhood is maximal over all independent sets of the graph. The core of \(G\) is defined to be the intersection of all maximum independent sets of \(G\), while \(\ker(G)\) denotes the intersection of all critical independent sets of \(G\). Previously [SIAM J. Discrete Math. 26, No. 1, 399--403 (2012; Zbl 1246.05122)] the authors showed that the kernel of \(G\) is a subset of its core. In the paper under review the authors present several structural properties of the kernel. In particular it is shown that the kernel is the union of inclusion minimal independent sets with positive difference number.