Foldings in graphs and relations with simplicial complexes and posets

We study dismantlability in graphs. In order to compare this notion to similar operations in posets (partially ordered sets) or in simplicial complexes, we prove that a graph G dismantles on a subgraph H if and only if H is a strong deformation retract of G. Then, by looking at a triangle relating graphs, posets, and simplicial complexes, we get a precise correspondence of the various notions of dismantlability in each framework. As an application, we study the link between the graph of morphisms from a graph G to a graph H and the polyhedral complex Hom(G, H): this gives a more precise statement about well-known results concerning the polyhedral complex Hom(G, H) and its relation with foldings in G or H. (C) 2011 Elsevier B.V. All rights reserved.