2020/09/09 by Takahiro Matsushita, Matsushita, Takahiro · 1 citation
Computer Science · Mathematics · #Advanced Combinatorial Mathematics #Algebraic Topology (math.AT) #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Topological and Geometric Data Analysis
paper · pdf · doi:10.48550/arxiv.2009.04145
openalex publication_date 2020/09/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 τ(G) of G.