Bipartite graphs and best proximity pairs

DOI10.1007/S10958-022-06005-5arXiv2111.07289MaRDI QIDQ6382995FDOQ6382995

Authors: Karim Chaira, Aleksey A. Dovgoshey, Samih Lazaiz 

Publication date: 14 November 2021

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.

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)

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)