Geodesic Geometry on Graphs

16 February 2021
Nati Linial

Further Information: 

Part of the Oxford Discrete Maths and Probability Seminar, held via Zoom. Please see the seminar website for details.


We investigate a graph theoretic analog of geodesic geometry. In a graph $G=(V,E)$ we consider a system of paths $P=\{P_{u,v}| u,v\in V\}$ where $P_{u,v}$ connects vertices $u$ and $v$. This system is consistent in that if vertices $y,z$ are in $P_{u,v}$, then the sub-path of $P_{u,v}$ between them coincides with $P_{y,z}$. A map $w:E\to(0,\infty)$ is said to induce $P$ if for every $u,v\in V$ the path $P_{u,v}$ is $w$-geodesic. We say that $G$ is metrizable if every consistent path system is induced by some such $w$. As we show, metrizable graphs are very rare, whereas there exist infinitely many 2-connected metrizable graphs.

  • Combinatorial Theory Seminar