Stellenbosch University
On proximity and remoteness in directed
graphs
S. Mafunda\(^*\), University of
Johannesburg
J. Ai, Royal Holloway, University of
London
S. Gerke, Royal Holloway, University
of London
G. Gutin, Royal Holloway, University
of London
SAMS Subject Classification Number: 06
In a strong, finite digraph \(D\) of order \(n\), the distance \(d_D(u,v)\) from vertex \(u\) to vertex \(v\) is the length of a shortest \(u-v\) path in \(D\). The average distance \(\bar{\sigma}(x)\) of a vertex \(x\) of \(D\) is the arithmetic mean of the distances from \(x\) to all other vertices of \(D\). The remoteness \(\rho(D)\) and proximity \(\pi(G)\) of \(D\) are the maximum and the minimum of the average distances of the vertices of \(D\), respectively.
In 2021, Ai et al. [1] showed that for any pair of vertices in \(D\), their average distances can differ by no more than \(\frac{1}{2}(n-2)\). This suggests a natural question if there is a simple characterisation of all digraphs where all vertices have the same average distance.
In this talk, we discuss the above characterisation for strong tournaments and we further present an infinite family of non-regular strong digraphs \(D\) such that \(\rho(D)=\pi(D)\).
References
[1] J. Ai, S. Gerke, G. Gutin, and S. Mafunda, Proximity and remoteness in directed and undirected graphs. Discrete Math. 344 (2021), 1122–52.
