The Travelling Polytope Constant of a Product of Trees: An Answer to a Question of Genevois

The travelling polytope constant \(\operatorname{TP}(X)\) of a graph \(X\) compares the travelling salesman problem through a finite set \(F\) of vertices with the shortest way to sweep \(F\) by convex hulls which grow or shrink by one adjacent vertex at a time. A. Genevois introduced it in his thesis (2017), as the travelling salesman constant of a CAT(0) cube complex; he proved that it equals \(d/(2d-1)\) for \(\mathbb{Z}^d\) and lies in \([1/2,2/3]\cup\{1\}\) for unbounded median graphs of bounded degree, and asked for its value for a product of two trees. At the Oberwolfach workshop Median Geometry and Applications (2026) he asked again to compute it for products of (regular) trees. We show that \(\operatorname{TP}(T_1\times\dots\times T_d)=d'/(2d'-1)\), where \(d'\ge1\) is the number of factors of unbounded diameter, without any assumption on the degrees, and treat the remaining cases, in which all factors have finite diameter. So a product of \(d\) regular trees of degree at least \(2\) has constant \(d/(2d-1)\), as Genevois's guess for cocompact cube complexes predicts. The upper bound is Genevois's grid example for \(\mathbb{Z}^d\), placed on geodesic segments of the factors. The new part is the lower bound: by Genevois's formula, the shortest sweep has twice as many steps as there are hyperplanes separating two of the points, and Euler tours of the projected hulls give a \(1\)-Lipschitz map from a box onto the hull of the points, through which the classical strip bound for the travelling salesman problem in a cube applies. The values obtained were known values of the constant, so the note gives no new value; which values the constant takes on median graphs remains open. This is an unrefereed note.