Bipartite graphs and best proximity pairs

Abstract

We say that a bipartite graph $G(A,B)$ with fixed parts $A$, $B$ is proximinal if there is a semimetric space $(X,d)$ such that $A$ and $B$ are disjoint proximinal subsets of $X$ and all edges $\{a,b\}$ satisfy the equality $d(a,b)=\mathrm{dist}(A,B)$. It is proved that a bipartite graph $G$ is not isomorphic to any proximinal graph iff $G$ is finite and empty. It is also shown that the subgraph induced by all non-isolated vertices of a nonempty bipartite graph $G$ is a disjoint union of complete bipartite graphs iff $G$ is isomorphic to a nonempty proximinal graph for an ultrametric space.

arXiv comment20 pages, 2 figures