Characterization of connected graphs whose geodesic metric satisfies the Menger condition

Let GG be a nonempty connected graph. Write V(G)V(G) for its vertex set and dGd_G for its geodesic distance. Let MB\mathfrak{MB} denote the class of metric spaces (X,d)(X,d) such that

d(x,z)=d(x,y)+d(y,z)d(x,z)=d(x,y)+d(y,z)

whenever d(x,z)max{d(x,y),d(y,z)}d(x,z)\geqslant\max\{d(x,y),d(y,z)\}. The graph characterization conjecture. The metric space (V(G),dG)(V(G),d_G) belongs to MB\mathfrak{MB} if and only if one of the following holds: GG is isomorphic to a path; GG is isomorphic to the cycle C4C_4; GG is isomorphic to a ray RR; or GG is isomorphic to a double ray DRDR. This conjecture reformulates Menger's characterization in graph-theoretic language; the claimed classification connects the four-point metric condition with the global structure of connected graphs.

Sources & referencesView supporting material

Primary source

Oleksiy Dovgoshey, “Characterization of geodesic distance on infinite graphs”, arXiv:2408.02385 (2024).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.