Collapsibility of Non-Cover Complexes of Graphs

Let $G$ be a graph on the vertex set $V$. A vertex subset $W \subseteq V$ is a cover of $G$ if $V \setminus W$ is an independent set of $G$, and $W$ is a non-cover of $G$ if $W$ is not a cover of $G$. The non-cover complex of $G$ is a simplicial complex on $V$ whose faces are non-covers of $G$. Then...

Full description

Saved in:
Bibliographic Details
Published in:The Electronic journal of combinatorics 2020-01, Vol.27 (1)
Main Authors: Choi, Ilkyoo, Kim, Jinha, Park, Boram
Format: Article
Language:English
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Let $G$ be a graph on the vertex set $V$. A vertex subset $W \subseteq V$ is a cover of $G$ if $V \setminus W$ is an independent set of $G$, and $W$ is a non-cover of $G$ if $W$ is not a cover of $G$. The non-cover complex of $G$ is a simplicial complex on $V$ whose faces are non-covers of $G$. Then the non-cover complex of $G$ is the combinatorial Alexander dual of the independence complex of $G$. Aharoni asked if the non-cover complex of a graph $G$ without isolated vertices is $(|V(G)|-i\gamma(G)-1)$-collapsible where $i\gamma(G)$ denotes the independence domination number of $G$. Extending a result by the second author, who verified Aharoni's question in the affirmative for chordal graphs, we prove that the answer to the question is yes for all graphs.
ISSN:1077-8926
1077-8926
DOI:10.37236/8684