Graph of uv-Paths in Connected Graphs: Discrete and Computational Geometry, Graphs, and Games - Rivera-Campo, Eduardo (Thai Journal of Mathematics, 2023)
For a connected graph G and vertices u,v of G we define an abstract graph P(G_uv) whose vertices are the paths joining u and v in G, where paths S and T are adjacent if T is obtained from S by replacing a subpath S_xy of S with an internally disjoint subpath T_xy of T. Let C be a set of cycles of G; the uv-path graph of G defined by C is the spanning subgraph P_C(G_uv) of P(G_uv) in which two paths S and T are adjacent if and only if the unique cycle σ contained in ST lies in C. We prove that P(G_uv) is always connected and give a necessary condition and a sufficient condition for a graph P_C(G_uv) to be connected.