Greedoids on vertex sets of BB-joins of graphs

Vadim E. LevitEugen Mândrescu



Let Ψ(G)Ψ(G) be the family of all local maximum stable sets of graph GG, i.e., S∈Ψ(G)S∈Ψ(G) if SS is a maximum stable set of the subgraph induced by S∪N(S)S∪N(S), where N(S)N(S) is the neighborhood of SS. It was shown that Ψ(G)Ψ(G) is a greedoid for every forest GG. The cases of bipartite graphs, triangle-free graphs, and well-covered graphs. If G1G1, G2G2 are two disjoint graphs, and BB is a bipartite graph having E(B)E(B) as an edge set and bipartition {V(G1),V(G2)}{V(G1),V(G2)}, then by BB-join of G1,G2G1,G2 we mean the graph B(G1,G2)B(G1,G2) whose vertex set is V(G1)∪V(G2)V(G1)∪V(G2) and edge set is E(G1)∪E(G2)∪E(B)E(G1)∪E(G2)∪E(B). In this paper we present several necessary and sufficient conditions for Ψ(B(G1,G2))Ψ(B(G1,G2)) to form a greedoid, an antimatroid, and a matroid, in terms of Ψ(G1)Ψ(G1), Ψ(G2)Ψ(G2) and E(B)E(B).

Additional Information


Levit, Vadim E., Mândrescu, Eugen