Proximinal sets and connectedness in graphs

DOI10.1007/S10958-023-06502-1MaRDI QIDQ6113259zbMATH OpenOpenAlexFDO

Authors Karim Chaira, Aleksey A. Dovgoshey

Publication date 8 August 2023

Published in Journal of Mathematical Sciences (New York) (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2303.02739

zbMATH Keywords

best proximity pairbipartite graphconnected component of graphpathproximinal setsemimetric spaceultrametric space

Mathematics Subject Classification ID

Graph theory (05C99)

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

Review text

Let \(G(V,E)\) be a graph where \(V\neq \emptyset\) denotes the set of vertices and \(E\) denotes the set of edges. A bipartite graph \(G(A, B)\) with fixed parts \(A\) and \(B\) is said to be proximinal if there exists a semimetric space \((X, d)\) such that \(A\) and \(B\) are disjoint proximinal subsets of \(X\), and vertices \(a\in A\) and \(b\in B\) are adjacent if and only if \(d(a, b) = \operatorname{dist}(A, B)\). In [\textit{K. Chaira} et al., J. Math. Sci., New York 264, No. 4, 369--388 (2022; Zbl 1511.54016)], it was proved besides the main structure of bipartite graph that a bipartite graph \(G\) is not isomorphic to any proximinal graph if and only if \(G\) is finite and empty. In the paper [\textit{O. Dovgoshey} and \textit{R. Shanin}, J. Fixed Point Theory Appl. 25, No. 1, Paper No. 34, 31 p. (2023; Zbl 1505.05049)], it is characterized that the semimetric spaces whose proximinal graphs have either at most one edge or vertices of degree at most one only. The graph \(G\) is called path-proximinal graph if there is 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\). The vertices \(u, v\in V\) are adjacent if and only if \[ d(u, v) \leq \inf \{d(x, y): 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\). In this paper, authors continue to study the interaction between proximity and graphs by introducing path-proximinal graphs.

Recommendations

• Uniqueness of best proximity pairs and rigidity of semimetric spaces
• Bipartite graphs and best proximity pairs
• Proximity graphs inside large weighted graphs
• Evaluating the configuration and the travel efficiency on proximity graphs as transportation networks
• Best proximity point theorems on rectangular metric spaces endowed with a graph
• Proof of conjectures on remoteness and proximity in graphs
• scientific article; zbMATH DE number 808798
• Graph similarity and distance in graphs
• b-metric spaces with a graph and best proximity points for some contractions
• scientific article; zbMATH DE number 4174951

Cites work

• A theorem on best approximations
• Approximate selections, best approximations, fixed points, and invariant sets
• BEST APPROXIMATION AND BEST SIMULTANEOUS APPROXIMATION IN ULTRAMETRIC SPACES
• Best proximity pairs in ultrametric spaces
• Bipartite graphs and best proximity pairs
• Convex Sets and Nearest Points
• Graph theory
• scientific article; zbMATH DE number 3455838 (Why is no real title available?)
• Ultrametrics and Complete Multipartite Graphs
• Uniqueness of best proximity pairs and rigidity of semimetric spaces

Cited in

(2)

• Bipartite graphs and best proximity pairs
• scientific article; zbMATH DE number 5287420 (Why is no real title available?)

This page was built for publication: Proximinal sets and connectedness in graphs

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