Graphs with GP-connected medians

• 成果类型: Article
• 署名作者: Beneteau, Laurine; Chalopin, Jeremie; Chepoi, Victor; Vaxes, Yann
• 署名单位: Universite de Toulon; Centre National de la Recherche Scientifique (CNRS); Aix-Marseille Universite
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-023-01939-3
• 发表日期: 2024
• 页码: 369-420
• 关键词: fiber-complemented graphs; absolute retracts; Formal theory; complexes; location; index

摘要

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 = 2, we characterize the graphs in which, with respect to any non-negative weights, median sets always induce connected subgraphs in the pth power Gp of G. This extends some characterizations of graphs with connected medians (case p = 1) provided by Bandelt and Chepoi (SIAM J Discrete Math 15(2):268-282, 2002. https:// doi. org/10.1137/S089548019936360X). 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 G2-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.