MAXIMAL HEREDITARY KONIG-EGERVARY SET-SYSTEMS

A Konig-Egervary graph is a graph G satisfying alpha(G) + mu(G) = vertical bar V(G)vertical bar, where alpha(G) is the cardinality of a maximum independent set and mu(G) is the matching number of G. Such graphs are those that admit a matching between V(G) - boolean AND Gamma and boolean OR Gamma, where Gamma is a set-system comprised of maximum independent sets satisfying vertical bar boolean AND Gamma'vertical bar + vertical bar boolean OR Gamma'vertical bar = 2 alpha(G) for every set-system Gamma' subset of Gamma; we refer to set-systems satisfying this equality hereditarily as hereditary Konig-Egervaty set-systems (HKE set-systems, hereafter). In the current paper, we study the maximal HKE set-systems and invoke characterizations of HKE set-systems. We solve a problem of the author with Levit and Mandrescu, proving that a set-system is HKE if and only if it satisfies the above equality and is included in Omega(G) for some graph G. Generally, we cannot reconstruct the graph from Omega(G), the set of maximum independent sets. But we prove that if alpha(G) is a maximal HKE set-system and V(G) = boolean AND Omega(G), then G is a specific bipartite graph.