Distance $r$-domination number and $r$-independence complexes of graphs

Abstract

For $r\ge 1$, the $r$-independence complex of a graph $G$, denoted Ind${}_r(G)$, is a simplicial complex whose faces are subsets $A\subseteq V(G)$ such that each component of the induced subgraph $G[A]$ has at most $r$ vertices. In this article, we establish a relation between the distance $r$-domination number of $G$ and (homological) connectivity of Ind${}_r(G)$. We also prove that Ind${}_r(G)$, for a chordal graph $G$, is either contractible or homotopy equivalent to a wedge of spheres. Given a wedge of spheres, we also provide a construction of a chordal graph whose $r$-independence complex has the homotopy type of the given wedge.

14 pages