摘要 Abstract
若两个图参数在每个图 \( G \) 上彼此相差一个常数因子,则称它们是粗等价的。近期,一些图参数被证明与树长粗等价。回顾一下,图 \( G \) 的树分解 \({\cal T}(G)\) 的长度为其袋中最大直径,而 \( G \) 的树长 \( tl(G) \) 是所有树分解中长度的最小值。类似地,图 \( G \) 的路径分解 \({\cal P}(G)\) 的长度为其袋中最大直径,而 \( G \) 的路径长 \( pl(G) \) 是所有路径分解中长度的最小值。本文提出了一些与路径长粗等价的图参数。我们证明了图 \( G \) 的路径长较小当且仅当以下等价条件之一成立:(a) \( G \) 可以嵌入到无权的毛虫树(等价于路径宽度为一的图)中,并具有小的加性畸变;(b) 存在一个常数 \( r \geq 0 \),使得对于 \( G \) 的任意三元组顶点 \( u, v, w \),其中心为某一点的半径 \( r \) 的圆盘拦截了连接其余两点的所有路径;(c) \( G \) 具有小的 \( k \geq 0 \) 的 \( k \)-支配最短路径;(d) \( G \) 具有小的 \( k' \geq 0 \) 的 \( k' \)-支配对;(e) \( G \) 的某个幂 \( G^\mu \) (\( \mu \geq 0 \) 为一个小整数)是 AT-自由图(甚至是一个共比较图)。
Two graph parameters are said to be coarsely equivalent if they are within constant factors from each other for every graph $G$. Recently, several graph parameters were shown to be coarsely equivalent to tree-length. Recall that the length of a tree-decomposition ${\cal T}(G)$ of a graph $G$ is the largest diameter of a bag in ${\cal T}(G)$, and the tree-length $tl(G)$ of $G$ is the minimum of the length, over all tree-decompositions of $G$. Similarly, the length of a path-decomposition ${\cal P}(G)$ of a graph $G$ is the largest diameter of a bag in ${\cal P}(G)$, and the path-length $pl(G)$ of $G$ is the minimum of the length, over all path-decompositions of $G$. In this paper, we present several graph parameters that are coarsely equivalent to path-length. Among other results, we show that the path-length of a graph $G$ is small if and only if one of the following equivalent conditions is true: (a) $G$ can be embedded to an unweighted caterpillar tree (equivalently, to a graph of path-width one) with a small additive distortion; (b) there is a constant $r\ge 0$ such that for every triple of vertices $u,v,w$ of $G$, disk of radius $r$ centered at one of them intercepts all paths connecting two others; (c) $G$ has a $k$-dominating shortest path with small $k\ge 0$; (d) $G$ has a $k'$-dominating pair with small $k'\ge 0$; (e) some power $G^\mu$ of $G$ is an AT-free (or even a cocomparability) graph for a small integer $\mu\ge 0$.