Abstract:Cizma and Linial introduced graph metrizability as the problem of deciding whether every consistent system of prescribed paths in a graph can be realized by shortest paths for some positive edge lengths. They asked for a classification of the metrizable theta graphs. We give the complete classification. If $a\le b\le c$, then the theta graph $\Theta_{a,b,c}$ is metrizable if and only if $a\le 2$ or $(a,b,c)=(3,3,3)$. The non-metrizable direction follows from the known obstruction $\Theta_{3,3,4}$ and topological-minor closure. The positive direction is constructive. For the family $\Theta_{2,b,c}$, consistency forces certain same-arm and cross-arm choices to be Ferrers relations, and these relations are realized by one-dimensional potentials. The exceptional graph $\Theta_{3,3,3}$ is handled by a two-threshold version of the same construction. The proof is structural and does not rely on enumeration of path systems.
From: Guangfu Wang [view email]
[v1]
Mon, 15 Jun 2026 07:52:18 UTC (18 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。