Graph Operations that are Good for Greedoids

Details Graph Operations that are Good for Greedoids Graph Operations that are Good for Greedoids

2008-09-10

arxiv.org/abs/0809.1806v1

Mathematics

Combinatorics

8 pages, 4 figures

Scientific paper

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*{H_1,H_2,...,H_n} obtained by joining each vertex k of a graph X to all the vertices of a graph H_k.

Affiliated with

Also associated with

No associations

Rating

Graph Operations that are Good for Greedoids does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Graph Operations that are Good for Greedoids, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Graph Operations that are Good for Greedoids will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-161612