Proximity and remoteness in graphs: a survey (Q6546420)

The proximity \(\pi = \pi(G)\) of a connected graph \(G\) is the minimum, over all vertices, of the average distance from a vertex to all others. Similarly, the maximum is called the remoteness and is denoted by \(\rho = \rho(G)\). These two concepts were defined in 2006 [\textit{M. Aouchiche}, Comparaison automatisée d'invariants en théorie des graphes. Montréal, QC: École Polytechnique de Montréal (PhD Thesis) (2006); \textit{M. Aouchiche} et al., MATCH Commun. Math. Comput. Chem. 58, No. 2, 365--384 (2007; Zbl 1274.05235)]. Many researchers published a considerable number of papers on these concepts. This paper contains a survey of the research work done by various authors about the two graph invariants proximity and remoteness. This survey collects all the results related to proximity \(\pi\) and remoteness \(\rho\) and their relation with other spectral invariants published in different journals from 2006 to January 2024.\N\NOne can find the answers to the following questions in this paper.\N\begin{itemize}\N\item[(i)] What are the minimum and maximum values of \(\pi\) and \(\rho\) for given order \(n\)?\N\item[(ii)] Which extremal graphs are associated with these extremal values for a given order?\N\item[(iii)] How large can the difference \(\rho - \pi\) be?\N\item[(iv)] What are the Nordhaus-Gaddum inequalities for these invariants?\N\item[(v)] What are the relations between proximity and remoteness with minimum degree?\N\item[(vi)] What are the bounds for \(\pi\) and \(\rho\) in triangle-free and \(C_4\)-free graphs?\N\item[(vii)] When is \(\rho(D) = \pi(D)\)? (where \(D\) is a digraph).\N\item[(viii)] How to compare these invariants with the metric invariants of a graph like diameter, radius, average eccentricity, and other invariants.\N\end{itemize}