2025/10/09 by Sufiyan Mallu, Mallu, Sufiyan
Computer Science · Mathematics · #Interconnection Networks and Systems #Advanced Graph Theory Research #Graph theory and applications
paper · pdf · doi:10.48550/arxiv.2510.08841
Let \( D \) be a strongly connected digraph. The average distance of a vertex \( v \) in \( D \) is defined as the arithmetic mean of the distances from \( v \) to all other vertices in \( D \). The remoteness \( ρ(D) \) of \( D \) is the maximum of the average distances of the vertices in \( D \). In this paper, we provide a sharp upper bound on the remoteness of a strong digraph with given order, size, and vertex-connectivity. We then characterise the extremal digraphs that maximise remoteness among all strong digraphs of order \(n\), size at least \(m\), and vertex-connectivity \(κ\). Finally, we demonstrate that the upper bounds on the remoteness of a graph given its order, size, and connectivity constraints (see \citeDanMafMal2025) can be extended to a larger class of digraphs containing all graphs, the Eulerian digraphs.