Bipartite graphs and best proximity pairs

DOI10.1007/S10958-022-06005-5MaRDI QIDQ6382995arXivFDO

Authors Karim Chaira, Aleksey A. Dovgoshey, Samih Lazaiz

Publication date 14 November 2021

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Metric spaces, metrizability (54E35) Saturation in approximation theory (41A40)

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)=operatornamedist(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.

This page was built for publication: Bipartite graphs and best proximity pairs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6382995)