Collapsibility and homological properties of I -contractible transformations

Jesús F. Espinoza*, Martín Eduardo Frías-Armenta, Héctor A. Hernández-Hernández

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

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.

Original languageEnglish
Article number42
JournalBoletin de la Sociedad Matematica Mexicana
Volume28
Issue number2
DOIs
StatePublished - Jul 2022
Externally publishedYes

Bibliographical note

Funding Information:
The author J.-F. Espinoza acknowledges the financial support of PRODEP and of the Universidad de Sonora, through the research project “Métodos de Topología Combinatoria en el Análisis de Datos”. The authors acknowledges all the observations of the anonymous referee, which were really pertinent to improve the presentation of this work. Special thanks for the editor, for the support and assistant in the submitting and preparation of this paper.

Publisher Copyright:
© 2022, Sociedad Matemática Mexicana.

Keywords

  • Collapsible graph
  • Contractible transformations
  • Persistent homology
  • Vietoris–Rips complex

Fingerprint

Dive into the research topics of 'Collapsibility and homological properties of I -contractible transformations'. Together they form a unique fingerprint.

Cite this