Bounded-diameter tree-decompositions (Q6548028)

This article addresses tree decompositions and five graph invariants. A ``tree decomposition'' of a graph \(G\) is a covering \((B_t : t \in V(T))\) of \(V(G)\) where \(T\) is a tree such that for every edge \(uv \in E(G)\), there exists \(t \in V(T)\) with \(u, v \in B_t\), and such that for every path \(p\) in \(T\) with initial endpoints \(s, t \in V(T)\), if \(u\) is a vertex of \(p\) then \(B_s \cap B_t \subseteq B_u\). These sets \(B_t\) are called ``bags'', and the authors ask how small the diameter of these bags can be, as induced graphs (``inner diameter width'' or idw) or using the edge distances from \(G\)'s edge relation \(E(G)\) (``outer diameter width'' or odw).\par Meanwhile, for a graph \(G\), a tree \(T\) and a map \(\phi : V(G) \to V(T)\), the ``additive distortion'' (ad) of \(\phi\) is \(\max_{u,v} \vert d_G(u, v) - d_T(\phi(u), \phi(v))\vert \), where \(d_G\) and \(d_T\) are the edge-distance metrics on \(G\) and \(T\), respectively. And the ``McCarty-width'' (mcw) of a graph \(G\) is the least \(k\) such that for any vertices \(u, v, w \in V(G)\), there exists vertex \(x\) such that if the ball of radius \(k\) around \(x\) is removed from \(G\), no two of \(u\), \(v\), \(w\) are in the same component (if not themselves removed). Finally, for a cycle \(C\) in a graph \(G\) and a ``load'' \(F \subseteq E(C)\), say that \((C, F)\) is ``geodesic'' if, for every \(u, v \in V(C)\), \(d_G(u, v)\) is greater or equal to the minimal number of edges in \(F\) in either path from \(u\) to \(v\) in \(C\); let the ``geodesic loaded cycle'' number (glc) be the maximum of all cardinalities of loads of geodesic pairs \((C, F)\), \(C\) a cycle in \(G\).\par It turns out that for any of two of these invariants, idw, odw, glc, ad, and mcw, if we called our two chosen invariants inv1 and inv2, there exist positive constants \(A\) and \(B\) such that for all graphs \(G\), inv1\((G)/A - B \leq\) inv2\((G) \leq A\)inv2\((G) + B\). In particular, for any family of graphs with a fixed bound on glc, that family will have a fixed bound on odw.