Weak Graph Map Homotopy and Its Applications

Abstract

The authors introduce a notion of a weak graph map homotopy (they call it M-homotopy), discuss its properties and applications. They prove that the weak graph map homotopy equivalence between graphs coincides with the graph homotopy equivalence defined by Yau et al in 2001. The difference between them is that the weak graph map homotopy transformation is defined in terms of maps, while the graph homotopy transformation is defined by means of combinatorial operations. They discuss its advantages over the graph homotopy transformation. As its applications, they investigate the mapping class group of a graph and the 1-order M P-homotopy group of a pointed simple graph. Moreover, they show that the 1-order M P-homotopy group of a pointed simple graph is invariant up to the weak graph map homotopy equivalence.

Keywords

Weak graph map homotopy / Trivial vertex / Strong deformation retract / Mapping class group / M P-Homotopy group

References

[1] Babson E, Barcelo H, de Longueville M, Laubenbacher R. Homotopy theory of graphs. J. Algebr. Comb., 2006, 24(1): 31-44

[2] Barcelo H, Kramer X, Laubenbacher R, Weaver C. Foundations of a connectivity theory for simplicial complexes. Adv. Appl. Math., 2001, 26(2): 97-128

[3] Boulet R, Fieux E, Jouve B. Simplicial simple-homotopy of flag complexes in terms of graphs. Eur. J. Combin., 2010, 31(1): 161-176

[4] Chen B, Yau S T, Yeh Y N. Graph homotopy and Graham homotopy. Discrete Math., 2001, 241(1–3): 153-170

[5] Chih T, Scull L. A homotopy category for graphs. J. Algebr. Comb., 2021, 53(4): 1231-1251

[6] Dochtermann A. Hom complexes and homotopy theory in the category of graphs. Eur. J. Combin., 2009, 30(2): 490-509

[7] Dochtermann A. Homotopy groups of Hom complexes of graphs. J. Comb. Theory A, 2009, 116(1): 180-194

[8] Espinoza, J. F., Frías-Armenta, M. E. and Hernández, H. A., Homological properties of contractible transformations of graphs, 2018, arXiv:1808.07461.

[9] Grigor’yan, A., Lin, Y., Muranov, Y. and Yau, S. T., Homologies of path complexes and digraphs, 2012, arXiv:1207.2834.

[10] Grigor’yan A, Lin Y, Muranov Y, Yau S T. Homotopy theory for digraphs. Pure Appl. Math. Q., 2014, 10(4): 619-674

[11] Hatcher A. Algebraic Topology, 2002, Cambridge: Cambridge University Press

[12] Hellmuth M, Ostermeier L, Stadler P F. A survey on hypergraph products. Math. Comput. Sci., 2012, 6: 1-32

[13] Ivashchenko A V. Representation of smooth surfaces by graphs, Transformations of graphs which do not change the Euler characteristic of graphs. Discrete Math., 1993, 122: 219-233

[14] Ivashchenko A V. Contractible transformations do not change the homology groups of graphs. Discrete Math., 1994, 126: 159-170

[15] Ivashchenko A V. Graphs of spheres and tori. Discrete Math., 1994, 128: 247-255

[16] Ivashchenko A V. Some properties of contractible transformations on graphs. Discrete Math., 1994, 133: 139-145

[17] Ivashchenko A V, Yeh Y N. Minimal graphs of a torus, a projective plane and spheres and some properties of minimal graphs of homotopy classes. Discrete Math., 1994, 126: 171-178

[18] Kahle M. Topology of random clique complexes. Discrete Math., 2009, 309(6): 1658-1671

[19] Nogly D, Schladt M. Digital topology on graphs. Comput. Vis. Image Und., 1996, 63(2): 394-396

[20] Takahiro M. Homotopy types of the Hom complexes of graphs. Eur. J. Combin., 2017, 63: 216-226

[21] Yeh Y N. The generating polynomial and Euler characteristic of intersection graphs. Discrete Math., 1994, 131: 325-333