Irreducible nonmetrizable path systems in graphs

• Published in: Journal of graph theory 2023-01, Vol.102 (1), p.5-14
• Main Authors: Cizma, Daniel, Linial, Nati
• Format: Article
• Language: English
• Subjects: Apexes; Graphs; irreducibility; metrizability; Paley graphs; path systems; Shortest-path problems; Weighting functions
• ISSN: 0364-9024; 1097-0118
• DOI: 10.1002/jgt.22854

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\to {{\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.