Hereditary Konig Egervary Collections

Abstract

Let $G$ be a simple graph with vertex set $V(G)$. A subset $S$ of $V(G)$ is independent if no two vertices from $S$ are adjacent. The graph $G$ is known to be a Konig-Egervary (KE in short) graph if $\alpha (G)+\mu (G)=|V(G)|$, where $\alpha (G)$ denotes the size of a maximum independent set and $\mu (G)$ is the cardinality of a maximum matching. Let $\Omega (G)$ denote the family of all maximum independent sets. A collection $F$ of sets is an hke collection if $|\bigcup \Gamma |+|\bigcap \Gamma |=2\alpha$ holds for every subcollection $\Gamma$ of $F$. We characterize an hke collection and invoke new characterizations of a KE graph. We prove the existence and uniqueness of a graph $G$ such that $\Omega (G)$ is a maximal hke collection. It is a bipartite graph. As a result, we solve a problem of Jarden, Levit and Mandrescu \cite{jlm}, proving that $F$ is an hke collection if and only if it is a subset of $\Omega (G)$ for some graph $G$ and $|\bigcup F|+|\bigcap F|=2\alpha (F)$. Finally, we show that the maximal cardinality of an hke collection $F$ with $\alpha (F)=\alpha$ and $|\bigcup F|=n$ is $2^{n-\alpha }$.

20 Pages