On unique independent sets in graphs (Q1331985)

For a nonnegative integer \(k\), a subset \(I\) of the vertex set \(V(G)\) of a simple graph \(G\) is said to be \(k\)-independent if \(I\) is independent and every independent subset \(I'\) of \(G\) with \(| I'| \geq | I|- (k- 1)\) is a subset of \(I\). A \(k\)-independent set \(I\) is strong \(k\)-independent if \(V(G)- I\) is independent in \(G\). For \(0\leq \ell \leq k\), \(k\)-independence implies \(\ell\)-independence. A set is 0-independent iff it is an independent set of maximum size; a set is 1-independent iff it is a unique independent set, a concept investigated in [\textit{G. Hopkins} and \textit{W. Staton}, Graphs with unique maximum independent set, Discrete Math. 57, 245-251 (1985; Zbl 0583.05034)]. The authors characterize \(k\)-independent sets for (a) graphs in which every even cycle has a chord, (b) graphs in which every block is a complete graph or an odd cycle, and (c) bipartite graphs. They then generalize results of Hopkins and Staton, and of \textit{F. Harary} and \textit{M. D. Plummer} [On the core of a graph, Proc. Lond. Math. Soc., III. Ser. 17, 305-314 (1967; Zbl 0152.412)] in Theorem 8: For a positive integer \(k\) a tree \(T\) has a strong \(k\)-independent set iff the distance between any two vertices of degree at most \(k\) is even. Finally, they prove a ``Turán-type'' extremeal theorem for graphs containing a \(k\)-independent set, and provide examples of extremal graphs.