Minimal graphs for contractible and dismantlable properties

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

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review


The notion of a contractible transformation on a graph was introduced by Ivashchenko as a means to study molecular spaces arising from digital topology and computer image analysis, and more recently has been applied to topological data analysis. Contractible transformations involve a list of four elementary moves that can be performed on the vertices and edges of a graph, and it has been shown by Chen, Yau, and Yeh that these moves preserve the simple homotopy type of the underlying clique complex. A graph is said to be I-contractible if one can reduce it to a single isolated vertex via a sequence of contractible transformations. Inspired by the notions of collapsible and non-evasive simplicial complexes, in this paper we study certain subclasses of I-contractible graphs where one can collapse to a vertex using only a subset of these moves. Our main results involve constructions of minimal examples of graphs for which the resulting classes differ. We also relate these classes of graphs to the notion of k-dismantlable graphs and k-collapsible complexes, which also leads to a minimal counterexample to an erroneous claim of Ivashchenko from the literature. We end with some open questions.

Original languageEnglish
Article number113516
JournalDiscrete Mathematics
Issue number10
StatePublished - Oct 2023

Bibliographical note

Publisher Copyright:
© 2023 Elsevier B.V.


  • Contractible graph
  • Dismantlable graph
  • Elementary collapse
  • Graph homotopy
  • Simple homotopy


Dive into the research topics of 'Minimal graphs for contractible and dismantlable properties'. Together they form a unique fingerprint.

Cite this