Dominance complexes and vertex cover numbers of graphs

Abstract

The dominance complex $D(G)$ of a simple graph $G=(V,E)$ is the simplicial complex consisting of the subsets of $V$ whose complements are dominating. We show that the connectivity of $D(G)$ plus $2$ is a lower bound for the vertex cover number $\tau (G)$ of $G$.

arXiv comment6 pages, the title was slightly modified, final version, to appear in Journal of Applied and Computational Topology