Collapsibility and homological properties of I -contractible transformations

The family of I-contractible graphs and contractible transformations was defined by A. Ivashchenko in the mid-90s. In this paper we study the collapsibility and homological properties of the clique complex associated to I-contractible graphs. We show that for any graph in a special subfamily of the I-contractible graphs (the strong I-contractible ones) its clique complex is collapsible. Moreover, we present an algorithm that allows us to verify if any graph is strong I-contractible, as well as an algorithm to delete those vertices whose open neighborhood is also strong I-contractible. Finally, we show how to use these algorithms to compute the persistent homology of an arbitrary Vietoris–Rips complex for applications in topological data analysis.