Crowns in bipartite graphs

A set S⊆V(G) is stable (or independent) if no two vertices from S are adjacent. Let Ψ(G) be the family of all local maximum stable sets [V. E. Levit, E. Mandrescu, A new greedoid: the family of local maximum stable sets of a forest, Discr. Appl. Math. 124 (2002) 91–101] of graph G, i.e., S∈Ψ(G) if S is a maximum stable set of the subgraph induced by S∪N(S), where N(S) is the neighborhood of S. If I is stable and there is a matching from N(I) into I, then I is a crown of order |I|+|N(I)|, and we write I∈Crown(G) [F. N. Abu-Khzam, M. R. Fellows, M. A. Langston, W. H. Suters, Crown structures for vertex cover kernelization, Theory of Comput. Syst. 41 (2007) 411–430]. In this paper we show that Crown(G)⊆Ψ(G) holds for every graph, while Crown(G)=Ψ(G) is true for bipartite and very well-covered graphs. For general graphs, it is NP-complete to decide if a graph has a crown of a given order [C. Sloper. Techniques in Parameterized Algorithm Design. Ph.D. thesis, Department of Computer Science, University of Bergen, Norway, 2005]. We prove that in a bipartite graph G with a unique perfect matching, there exist crowns of every possible even order.