Strong homotopy induced by adjacency structure.

This paper generalizes the concept of SA -homotopy in finite topological adjacency category, which is introduced in our previous work, to graph category and discusses its properties. We prove that every SA -strong deformation retract of a simple graph G could be obtained by removing trivial vertices one by one, which makes it possible to allow an iterative algorithm of finding all SA -strong deformation retracts of G. We also obtain that two simple graphs are SA -homotopy equivalent if and only if they have graph isomorphic cores. Compared with the graph homotopy transformation defined by S.T. Yau et al. and the s -homotopy transformation defined by R. Boulet et al., the main advantage of SA -homotopy transformation is that it could reflect correspondences between vertices, and hence it more accurately describe the transformation process than the graph homotopy transformation and s -homotopy transformation. As an application of SA -homotopy on graphs, we introduce the mapping class group of a graph, which also shows its advantage over the graph homotopy transformation and the s -homotopy transformation. [ABSTRACT FROM AUTHOR]