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
    Commented 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
    Commented Jun 15, 2015 at 6:38

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .