Geodesic geometry on graphs

Abstract: We investigate a graph theoretic analog of geodesic geometry. In a graph G=(V,E) we consider a system of paths $P=\{Pu,v | u,v \in V\}$ where $Pu,v$ connects vertices u and v. This system is consistent in that if vertices y,z are in $Pu,v$, then the sub-path of $Pu,v$ between them coincides with $Py,z$. A map $w:E \to (0,\infty)$ is said to induce P if for every $u,v \in V$ the path $Pu,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.

Joint work with my student Daniel Cizma

combinatorics

Audience: researchers in the topic

Extremal and probabilistic combinatorics webinar

Series comments: We've added a password: concatenate the 6 first prime numbers (hence obtaining an 8-digit password).