Skip to main content
3 of 3
added 9 characters in body

Strongly minimal covering subsets of $\text{Ind}(G)$

Let $G=(V,E)$ be an undirected, simple graph. Let $\text{Ind}(G)$ be the set of independent subsets of $V(G)$. We say that $K\subseteq \text{Ind}(G)$ is a cover (by independent subsets) if $\bigcup K = V(G)$ and denote the collection of all such covers with $\text{CovInd}(G)$.

We call a cover $M\in \text{CovInd}(G)$ strongly minimal if for all $K\in \text{CovInd}(G)$ we have $$|M\setminus K| \leq |K\setminus M|.$$ It is easy to show that strongly minimal covers are minimal elements of $\text{CovInd}(G)$ with respect to set inclusion. It's also easy to see that the cardinality of any strongly minimal cover equals $\text{min}\{|C|: C\in\text{CovInd}(G)\}$. (Both statements are valid for finite as well as infinite graphs.)

Question. Does every graph have a strongly minimal cover by independent subsets? (The answer is trivially positive for finite graphs.)