Irreducible nonmetrizable path systems in graphs. Issue 1 (23rd June 2022)

• Record Type: Journal Article
• Authors: Cizma, Daniel; Linial, Nati
• Is Part Of: Journal of graph theory. Volume 102:Issue 1(2023)
• Page Start: 5
• Page End: 14
• Publication Date: 2022-06-23
• Subjects: irreducibility -- metrizability -- Paley graphs -- path systems; Graph theory -- Periodicals; 511
• DOI: 10.1002/jgt.22854
• Languages: English
• ISSNs: 0364-9024

Abstract

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