2008/09/10 by Vadim E. Levit, Levit, Vadim E., Eugen Mandrescu +1
Computer Science · Mathematics · #05C69 (Primary) 05B35 #90C27 (Secondary) #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #cs.DM #math.CO #msc:05B35 #msc:05C69 #msc:90C27
paper · pdf · doi:10.48550/arxiv.0809.1806
8 pages, 4 figures
arxiv created 2008/09/10 · arxiv updated 2011/01/25
S is a local maximum stable set of a graph G, if the set S is a maximum stable set of the subgraph induced by its closed neighborhood. In (Levit, Mandrescu, 2002) we have proved that the family of all local maximum stable sets is a greedoid for every forest. The cases of bipartite graphs and triangle-free graphs were analyzed in (Levit, Mandrescu, 2004) and (Levit, Mandrescu, 2007), respectively. In this paper we give necessary and sufficient conditions for the family of all local maximum stable sets of a graph G to form a greedoid, where G is: (a) the disjoint union of a family of graphs; (b) the Zykov sum of a family of graphs, or (c) the corona X*H1,H2,...,Hn obtained by joining each vertex k of a graph X to all the vertices of a graph Hk.