TY - JOUR

T1 - Minimal graphs for contractible and dismantlable properties

AU - Dochtermann, Anton

AU - Espinoza, Jesús F.

AU - Frías-Armenta, Martín Eduardo

AU - Hernández, Héctor A.

N1 - Publisher Copyright:
© 2023 Elsevier B.V.

PY - 2023/10

Y1 - 2023/10

N2 - 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.

AB - 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.

KW - Contractible graph

KW - Dismantlable graph

KW - Elementary collapse

KW - Graph homotopy

KW - Simple homotopy

UR - http://www.scopus.com/inward/record.url?scp=85161685865&partnerID=8YFLogxK

U2 - 10.1016/j.disc.2023.113516

DO - 10.1016/j.disc.2023.113516

M3 - Artículo

AN - SCOPUS:85161685865

SN - 0012-365X

VL - 346

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 10

M1 - 113516

ER -