MAXIMAL HEREDITARY KÖNIG-EGERVÁRY SET-SYSTEMS
A König-Egerváry graph is a graph G satisfying where is the cardinality of a maximum independent set and is the matching number of G. Such graphs are those that admit a matching between and where Γ is a set-system comprised of maximum independent sets satisfying for every set-system we refer to set-systems satisfying this equality hereditarily as hereditary König-Egerváry 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 for some graph G.
Generally, we cannot reconstruct the graph from the set of maximum independent sets. But we prove that if is a maximal HKE set-system and then G is a specific bipartite graph.
König-Egerváry graphs, independent sets, set-systems.