Irreducible nonmetrizable path systems in graphs. Issue 1 (23rd June 2022) - Cizma, Daniel; Linial, Nati
Abstract: A path system P P in a graph G = ( V, E ) G=(V, E) is a collection of paths with a unique u v uv path for every two vertices u, v ∈ V u, vV . We say that P P is consistent if for any path P ∈ P PP, every subpath of P P is also in P P . It is metrizable if there exists a positive weight function w : E → R > 0 w:E→ R_0 such that P P is comprised of w w ‐shortest paths. We call P P irreducible if there does not exist a partition V = A ⊔ B V=AB such that P P restricts to a path system on both G [ A ] G[A] and G [ B ] G[B] . In this paper, we construct an infinite family of nonmetrizable irreducible consistent path systems on certain Paley graphs.