论文标题
$ g^p $连接的中位数
Graphs with $G^p$-connected medians
论文作者
论文摘要
带有加权顶点的图$ g $的中值是所有顶点的集合$ x $最小化加权距离的总和，从$ x $到$ g $的顶点。对于任何整数$ p \ ge 2 $，我们表征了这些图表，其中任何非负权重的中位数始终在$ p $ th power $ g^p $ of $ g $中始终诱导连接的子图。这扩展了Bandelt and Chepoi（2002）提供的连接中位数（案例$ p = 1 $）的图表的一些特征。任何$ p $都可以在多项式时间内测试特征条件。我们还表明，公制图理论中的几类图形，包括桥接图（以及弦弦图），带有凸球，富裕图和双分部分绝对缩回的图形具有$ g^2 $连接的中位数。扩展了带状图和chepoi的结果，即矩形的基础图是带有连接的中位数的图形，我们表征了约翰逊图的等距亚图和带有连接的中位数的一半立方体。
The median of a graph $G$ with weighted vertices is the set of all vertices $x$ minimizing the sum of weighted distances from $x$ to the vertices of $G$. For any integer $p\ge 2$, we characterize the graphs in which, with respect to any non-negative weights, median sets always induce connected subgraphs in the $p$th power $G^p$ of $G$. This extends some characterizations of graphs with connected medians (case $p=1$) provided by Bandelt and Chepoi (2002). The characteristic conditions can be tested in polynomial time for any $p$. We also show that several important classes of graphs in metric graph theory, including bridged graphs (and thus chordal graphs), graphs with convex balls, bucolic graphs, and bipartite absolute retracts, have $G^2$-connected medians. Extending the result of Bandelt and Chepoi that basis graphs of matroids are graphs with connected medians, we characterize the isometric subgraphs of Johnson graphs and of halved-cubes with connected medians.
