Graph Operations that are Good for Greedoids - Mathematics > CombinatoricsReportar como inadecuado




Graph Operations that are Good for Greedoids - Mathematics > Combinatorics - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

Abstract: S is a local maximum stable set of a graph G, if the set S is a maximumstable set of the subgraph induced by its closed neighborhood. In Levit,Mandrescu, 2002 we have proved that the family of all local maximum stablesets is a greedoid for every forest. The cases of bipartite graphs andtriangle-free graphs were analyzed in Levit, Mandrescu, 2004 and Levit,Mandrescu, 2007, respectively. In this paper we give necessary and sufficientconditions for the family of all local maximum stable sets of a graph G to forma greedoid, where G is: a the disjoint union of a family of graphs; b theZykov sum of a family of graphs, or c the corona X*{H 1,H 2,

.,H n} obtainedby joining each vertex k of a graph X to all the vertices of a graph H k.



Autor: Vadim E. Levit, Eugen Mandrescu

Fuente: https://arxiv.org/







Documentos relacionados