Homotopy in graphs

• Main Author: Alegado, Felix L.
• Format: text
• Language: English
• Published: Animo Repository 1999
• Subjects: Graph theory; Homotopy theory; Topology
• Online Access: https://animorepository.dlsu.edu.ph/etd_masteral/2025
• Institution: De La Salle University

This thesis is an exposition of Sections 1 to 7 of the article entitled Homotopy in Q-Polynomial Distance-Regular Graphs by Heather A. Lewis submitted to Discrete Mathematics. The aforementioned article constitutes the first two chapters of Lewis' dissertation Homotopy and Distance-Regular Graphs , University of Wisconsin Madison, U.S.A., 1997.Let G denote an undirected graph without loops or multiple edges. Fix a vertex x in G, and consider the set u/(x) of all closed paths in G with base vertex x. We define a relation on this set, called homotophy, and prove that it is an equivalence relation. We denote the equivalence classes by minimum degree (x) and show that path concatenation induces a group structure on minimum degree (x). We define essential length of an element in minimum degree (x), and using this concept, we define a collection of subgroups minimum degree (x,i).Now, suppose x, y are vertices in G, and suppose there exists a path from x to y. We show the groups minimum degree (x) and minimum degree (y) are isomorphic, and that the isomorphism preserves essential length.We define a geodesic path and prove a sufficient condition for a path to be geodesic. Finally, we assume G is finite and connected with diameter d. We find an upper bound for the length of a geodesic closed path. We prove that for any fix vertex x, minimum degree (x,2d+1)=minimum degree (x).