Proximinal sets and connectedness in graphs

Abstract

Let $G$ be a graph with a vertex set $V$. The graph $G$ is path-proximinal if there are a semimetric $d:V\times V\to [0,\infty [$ and disjoint proximinal subsets of the semimetric space $(V,d)$ such that $V=A\cup B$, and vertices $u$, $v\in V$ are adjacent iff \[ d(u, v) \leqslant \inf \{d(x, y) \colon x \in A, y \in B\}, \] and, for every $p\in 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$.

arXiv comment20 pages, 2 figures