2019/04/09 by Jinha Kim, Kim, Jinha
Computer Science · Mathematics · #Advanced Combinatorial Mathematics #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Topological and Geometric Data Analysis
paper · pdf · doi:10.48550/arxiv.1904.04519
openalex publication_date 2019/04/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let G be a graph on V. A vertex subset S ⊂ V is called a cover of G if its complement is an independent set, and S is called a noncover if it is not a cover of G. A noncover complex NC(G) of G is the simplicial complex on V whose faces are noncovers of G. The independence domination number iγ(G) of G is the minimum integer k such that every independent set of G can be dominated by k vertices. In this note, we prove that NC(G) is (|V|- iγ(G)-1)-collapsible.