2
$\begingroup$

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.)

Improve this question
$\endgroup$
2
  • $\begingroup$ I am sorry, but why a trivial cover of $V(G)$ by one-vertex sets is not strongly minimal? It violates some restrictions? For instance, the family $\text{Ind(G)}$ consists of maximal independent subsets? $\endgroup$
    – Alex Ravsky
    Jun 13, 2015 at 15:55
  • 1
    $\begingroup$ Consider the graph $G$ with $V(G) = \{0,1\}$ and $E(G) = \emptyset$. Then the cover $M:=\{\{0\},\{1\}\}$ is not strongly minimal: Let $K:=\{\{0,1\}\}$. Then we have $|M\setminus K| = 2>1= |K\setminus M|$. $\endgroup$
    – Dominic van der Zypen
    Jun 15, 2015 at 6:38

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.