Bounded-diameter tree-decompositions
Planar graphs; geometric and topological aspects of graph theory (05C10) Distance in graphs (05C12) Graph representations (geometric and intersection representations, etc.) (05C62) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)
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.
- Acylindrical group actions on quasi-trees
- Additive Tree Spanners
- Connected tree-width
- Constant approximation algorithms for embedding graph metrics into trees and outerplanar graphs
- Constructing group actions on quasi-trees and applications to mapping class groups
- Geometry of pseudocharacters.
- Graph minors. V. Excluding a planar graph
- Polynomial bounds for the grid-minor theorem
- Towards tight(er) bounds for the excluded grid theorem
- Tree approximation in quasi-trees
- Tree-chromatic number
- Tree-decompositions with bags of small diameter
This page was built for publication: Bounded-diameter tree-decompositions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6548028)
