Irreducible nonmetrizable path systems in graphs. Issue 1 (23rd June 2022) - Cizma, Daniel; Linial, Nati
Abstract: A path system P ${\mathscr{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, v\in V$ . We say that P ${\mathscr{P}}$ is consistent if for any path P ∈ P $P\in {\mathscr{P}}$, every subpath of P $P$ is also in P ${\mathscr{P}}$ . It is metrizable if there exists a positive weight function w : E → R > 0 $w:E→ {{\mathbb{R}}}_{\gt 0}$ such that P ${\mathscr{P}}$ is comprised of w $w$ ‐shortest paths. We call P ${\mathscr{P}}$ irreducible if there does not exist a partition V = A ⊔ B $V=A\bigsqcup B$ such that P ${\mathscr{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.