Remoteness, order, size and connectivity constraints in digraphs

Basic Information

• Paper ID: 2510.08841
• Title: Remoteness, order, size and connectivity constraints in digraphs
• Author: Sufiyan Mallu (University of Johannesburg, South Africa)
• Classification: math.CO (Combinatorics)
• Publication Date: October 13, 2025 (arXiv preprint)
• Paper Link: https://arxiv.org/abs/2510.08841

Abstract

This paper investigates the remoteness problem in strongly connected directed graphs. For a strongly connected digraph $D$, the average distance of a vertex $v$ is defined as the arithmetic mean of distances from $v$ to all other vertices, while the remoteness $\rho(D)$ of $D$ is defined as the maximum average distance over all vertices. The paper provides tight upper bounds on the remoteness of strongly connected digraphs with given order, size, and vertex connectivity, characterizes the extremal digraphs that maximize remoteness among all strongly connected digraphs with order $n$, size at least $m$, and vertex connectivity $\kappa$, and proves that upper bounds on remoteness for undirected graphs with respect to order, size, and connectivity constraints can be generalized to a larger class of digraphs—Eulerian digraphs.

Research Background and Motivation

1. Research Problem: Although distance problems in graphs have been extensively studied, research on distances in directed graphs remains relatively limited, particularly regarding the exploration of proximity and remoteness concepts in digraphs.
2. Problem Significance:
   • Distance parameters hold a fundamental position in graph theory with important applications in network analysis, algorithm design, and related fields
   • Directed graphs more accurately model asymmetric relationships in real-world scenarios, such as transportation networks and social networks
   • Extremal problems under connectivity constraints possess significant theoretical value
3. Limitations of Existing Approaches:
   • Ai et al. 1 first extended proximity and remoteness concepts to digraphs, but related research remains limited
   • Existing results primarily focus on cases considering only order constraints, lacking results that simultaneously account for size and connectivity
4. Research Motivation: This paper aims to fill gaps in the theory of digraph remoteness, establishing more precise bounds and characterizing extremal structures.

Core Contributions

1. Establishment of New Upper Bounds: Provides tight upper bounds on remoteness for $\kappa$-connected strongly connected digraphs with given order, size, and vertex connectivity
2. Characterization of Extremal Structures: Completely characterizes extremal digraphs achieving the remoteness upper bound—$\kappa$-connected path-complete digraphs
3. Generalization of Existing Results: Proves that remoteness upper bounds for undirected graphs can be generalized to Eulerian digraphs, a larger graph class
4. Constructive Proofs: Demonstrates the tightness of obtained bounds through explicit construction of extremal graph families

Methodology Details

Task Definition

Input: Strongly connected digraph $D$ and its parameters (order $n$, size $m$, vertex connectivity $\kappa$) Output: Upper bound on remoteness $\rho(D)$Constraints: $D$ must be a $\kappa$-connected strongly connected digraph

Core Concepts

1. Average Distance: The average distance of vertex $v$ is defined as $\sigma(v,D) = \frac{1}{n-1}\sum_{w \in V(D)} d_D(v,w)$
2. Remoteness: The remoteness of a digraph is defined as $\rho(D) = \max_{v \in V(D)} \sigma(v,D)$
3. $\kappa$-Connected Path-Complete Digraph: A digraph of the form $K_1 \overleftarrow{+} [\overleftrightarrow{K_\kappa}]^\ell \overleftarrow{+} \overleftrightarrow{K_a} \overleftarrow{+} \overleftrightarrow{K_b}$ where $a \geq \kappa$.

Main Technical Methods

1. Extremal Analysis: Establishes structural constraints by analyzing the distance distribution of vertices maximizing remoteness
2. Inductive Construction: Progressively proves that extremal graphs must possess specific path-complete structures
3. Size Optimization: Analyzes maximum size constraints of graphs while maintaining fixed remoteness

Key Lemmas

Lemma 3.1:

• (a) For any $\kappa$-connected path-complete digraph $H$, adding any arc decreases its remoteness
• (b) Strict size-remoteness trade-off relationships exist between distinct $\kappa$-connected path-complete strongly connected digraphs
• (c) Given $n, \kappa$, necessary and sufficient conditions exist for the existence of $\kappa$-connected path-complete strongly connected digraphs of specific sizes

Experimental Setup

This paper is purely theoretical research without experimental verification, relying instead on rigorous mathematical proofs to validate result correctness.

Proof Strategy

1. Existence Proofs: Constructs specific extremal graph families
2. Uniqueness Proofs: Establishes uniqueness of extremal graph structures
3. Tightness Verification: Verifies tightness of bounds through concrete examples

Main Results

Core Theorem

Theorem 3.2: Let $D$ be a $\kappa$-connected strongly connected digraph with order $n$ and size $m$, where $m \leq n^2 - 2n - 1$. Then $\rho(D) \leq \rho(DPK_{n,m,\kappa})$

Equality holds if and only if $D = DPK_{n,m,\kappa}$ when $m \equiv (n^2-2n-1) \pmod{\kappa}$ and specific conditions are satisfied.

Specific Bounds

Corollary 3.3: Under appropriate conditions, $\rho(D) \leq \frac{n}{\kappa} + 2 - \frac{1}{\kappa} - \frac{\kappa-1}{n-1} - \frac{m^*}{\kappa(n-1)}$

where $m^*$ is the smallest integer satisfying $m^* \geq m$ and $m^* \equiv (n^2-2n-1) \pmod{\kappa}$.

Results for Eulerian Digraphs

Theorem 4.3: Let $D$ be a $\kappa$-connected Eulerian digraph with order $n$ and size at least $2m_0$. Then $\rho(D) \leq \frac{n}{2\kappa} + 2 - \frac{1}{\kappa} - \frac{\kappa-1}{n-1} - \frac{m_0}{\kappa(n-1)}$

Technical Innovations

1. Completeness of Structural Characterization: Not only provides upper bounds but completely characterizes extremal structures achieving these bounds
2. Handling Multiple Parameter Constraints: Simultaneously addresses constraints from order, size, and connectivity parameters
3. Generalization from Undirected to Directed Graphs: Cleverly exploits properties of Eulerian digraphs to generalize undirected graph results to digraphs
4. Introduction of Modular Arithmetic Conditions: Discovers modular arithmetic conditions that size parameters must satisfy

Related Work

Historical Development

1. Zelinka 29 and Aouchiche, Hansen 4: Established fundamental upper bounds on remoteness for connected graphs: $\rho(G) \leq n/2$
2. Ai et al. 1: Generalized remoteness concept to directed graphs
3. Entringer et al. 18: Considered size constraints on graphs
4. Dankelmann et al. 15: Established remoteness bounds for undirected graphs with connectivity constraints

Positioning of This Paper's Contributions

This is the second paper specifically studying remoteness in directed graphs, filling important gaps in digraph theory and successfully generalizing precise results from undirected graphs to a broader class of digraphs.

Conclusions and Discussion

Main Conclusions

1. Establishes tight upper bounds on remoteness for $\kappa$-connected strongly connected digraphs
2. Completely characterizes extremal graph structures ($\kappa$-connected path-complete digraphs)
3. Proves that remoteness bounds for undirected graphs can be generalized to Eulerian digraphs

Theoretical Significance

• Enriches distance theory for directed graphs
• Provides new theoretical tools for network analysis
• Establishes bridges between undirected and directed graph theories

Future Directions

1. Study remoteness in more general classes of directed graphs
2. Explore relationships between remoteness and other graph parameters
3. Consider weighted directed graphs

In-Depth Evaluation

Strengths

1. Theoretical Completeness: Provides not only bounds but complete characterization of extremal structures
2. Technical Depth: Employs sophisticated proof techniques, particularly in handling digraph complexity
3. Tightness of Results: All major results are tight, indicating optimality of bounds
4. Ingenuity of Generalization: The method of generalizing undirected graph results to digraphs via Eulerian digraphs is creative

Limitations

1. Application Scope: Primarily theoretical results; practical applications require further exploration
2. Computational Complexity: Does not discuss computational complexity of related problems
3. Parameter Range: Some results require satisfaction of specific modular arithmetic conditions, limiting applicability

Impact

1. Theoretical Contribution: Establishes important foundations for digraph distance theory
2. Methodological Value: Proof techniques may apply to other digraph problems
3. Subsequent Research: Provides framework for further research on other distance parameters in digraphs

Applicable Scenarios

1. Centrality measures in network analysis
2. Structural analysis of directed graphs
3. Extremal graph theory research
4. Theoretical bound analysis in algorithm design

References

The paper cites 29 related references covering major research achievements in distance problems in graph theory, particularly:

• 1 Pioneering work by Ai et al. on proximity and remoteness in directed graphs
• 15 Recent results by Dankelmann et al. on remoteness in undirected graphs
• 29 Early work by Zelinka on remoteness

Overall Assessment: This is a high-quality theoretical paper making substantial contributions to the important but relatively nascent research field of digraph remoteness. The paper demonstrates high technical level with complete and tight results, establishing solid foundations for subsequent research in this area.