2023/03/05 by Karim Chaira, Oleksiy Dovgoshey, Chaira, Karim +1
Computer Science · #05C60 #05C62 #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #FOS: Mathematics #General Topology (math.GN) #Primary: 54E35 #Secondary: 54E05
paper · pdf · doi:10.48550/arxiv.2303.02739
openalex publication_date 2023/03/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let G be a graph with a vertex set V. The graph G is path-proximinal if there are a semimetric d \colon V × V → [0, ∞[ and disjoint proximinal subsets of the semimetric space (V, d) such that V = A ∪ B, and vertices u, v ∈ V are adjacent iff d(u, v) \leqslant inf \d(x, y) \colon x ∈ A, y ∈ B\, and, for every p ∈ V, there is a path connecting A and B in G, and passing through p. It is shown that a graph is path-proximinal if and only if all its vertices are not isolated. It is also shown that a graph is simultaneously proximinal and path-proximinal for an ultrametric if and only if the degree of every its vertex is equal to 1.