pith. sign in

arxiv: 1904.04519 · v1 · pith:MYVPEHK3new · submitted 2019-04-09 · 🧮 math.CO

Collapsibility of noncover complexes of chordal graphs

classification 🧮 math.CO
keywords noncovercalledcomplexcovergammaindependentsubsetchordal
0
0 comments X
read the original abstract

Let $G$ be a graph on $V$. A vertex subset $S \subset 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\gamma(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\gamma(G)-1)$-collapsible.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.