2025-11-17T15:31:13.202496

Remoteness, order, size and connectivity constraints in digraphs

Mallu

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 \cite{DanMafMal2025}) can be extended to a larger class of digraphs containing all graphs, the Eulerian digraphs.

academic

有向グラフにおける遠隔性、位数、サイズおよび連結性制約

基本情報

論文ID: 2510.08841
タイトル: Remoteness, order, size and connectivity constraints in digraphs
著者: Sufiyan Mallu（南アフリカ、ヨハネスブルグ大学）
分類: math.CO（組合数学）
発表日: 2025年10月13日（arXiv プレプリント）
論文リンク: https://arxiv.org/abs/2510.08841

摘要

本論文は強連結有向グラフの遠隔性(remoteness)問題を研究している。強連結有向グラフ $D$ において、頂点 $v$ の平均距離は $v$ から他のすべての頂点への距離の算術平均として定義され、 $D$ の遠隔性 $\rho(D)$ はすべての頂点の平均距離の最大値として定義される。本論文は、与えられた位数、サイズおよび頂点連結性を持つ強有向グラフの遠隔性に対する厳密な上界を提供し、位数 $n$ 、サイズ少なくとも $m$ 、頂点連結性 $\kappa$ のすべての強有向グラフの中で遠隔性を最大化する極値有向グラフを特徴付け、無向グラフの位数、サイズおよび連結性制約に関する遠隔性上界が、すべてのグラフを含むより大きな有向グラフのクラス——オイラー有向グラフ——に推広可能であることを証明している。

研究背景と動機

研究課題：グラフにおける距離問題は広く研究されているが、有向グラフにおける距離の研究は相対的に不足しており、特に近接性(proximity)および遠隔性の概念の有向グラフへの応用はまだ十分に探索されていない。
問題の重要性：
- 距離パラメータはグラフ理論において基礎的な地位を占め、ネットワーク分析やアルゴリズム設計などの分野に重要な応用を持つ
- 有向グラフはより正確に現実世界の非対称的関係（交通ネットワーク、ソーシャルネットワークなど）をモデル化できる
- 連結性制約下の極値問題は重要な理論的価値を有する
既存手法の限界：
- Aiら1が初めて近接性および遠隔性の概念を有向グラフに拡張したが、関連研究はまだ限定的である
- 既存の結果は主に位数制約のみを考慮する場合に集中しており、サイズと連結性を同時に考慮する結果が不足している
研究動機：本論文は有向グラフの遠隔性理論の空白を埋め、より精密な界限と極値構造の特徴付けを確立することを目指している。

核心的貢献

新しい上界の確立： $\kappa$ -連結強有向グラフに対して、与えられた位数、サイズおよび頂点連結性下での遠隔性の厳密な上界を提供
極値構造の特徴付け：遠隔性上界を達成する極値有向グラフ—— $\kappa$ -連結経路完全有向グラフ——を完全に特徴付け
既存結果の推広：無向グラフの遠隔性上界がオイラー有向グラフというより大きなグラフのクラスに推広可能であることを証明
構成的証明の提供：具体的な極値グラフ族の構成を通じて、得られた界限の厳密性を証明

方法の詳細

タスク定義

入力：強連結有向グラフ $D$ およびそのパラメータ（位数 $n$ 、サイズ $m$ 、頂点連結性 $\kappa$ ）出力：遠隔性 $\rho(D)$ の上界 制約条件： $D$ は $\kappa$ -連結強有向グラフでなければならない

核心概念

平均距離：頂点 $v$ の平均距離は以下のように定義される $\sigma(v,D) = \frac{1}{n-1}\sum_{w \in V(D)} d_D(v,w)$
遠隔性：有向グラフの遠隔性は以下のように定義される $\rho(D) = \max_{v \in V(D)} \sigma(v,D)$
$\kappa$ -連結経路完全有向グラフ：以下の形式の有向グラフ $K_1 \overleftarrow{+} [\overleftrightarrow{K_\kappa}]^\ell \overleftarrow{+} \overleftrightarrow{K_a} \overleftarrow{+} \overleftrightarrow{K_b}$ ここで $a \geq \kappa$ 。

主要な技術的手法

極値分析：遠隔性を最大化する頂点の距離分布を分析することで、構造制約を確立
帰納的構成：段階的に極値グラフが特定の経路完全構造を持つことを証明
サイズ最適化：固定された遠隔性の下で、グラフの最大サイズ制約を分析

主要補題

補題 3.1：

(a) $\kappa$ -連結経路完全有向グラフ $H$ に対して、任意の弧を追加すると遠隔性が減少する
(b) 2つの異なる $\kappa$ -連結経路完全強有向グラフ間には厳密なサイズ-遠隔性トレードオフが存在する
(c) 与えられた $n, \kappa$ に対して、特定のサイズの $\kappa$ -連結経路完全強有向グラフが存在するための必要十分条件が存在する

実験設定

本論文は純粋な理論研究であり、実験検証は含まれず、厳密な数学的証明を通じて結果の正確性を検証している。

証明戦略

存在性証明：具体的な極値グラフ族の構成
一意性証明：極値グラフの構造の一意性を証明
厳密性検証：具体例を通じて界限の厳密性を検証

主要結果

核心定理

定理 3.2： $D$ を位数 $n$ 、サイズ $m$ の $\kappa$ -連結強有向グラフとし、 $m \leq n^2 - 2n - 1$ とする。このとき $\rho(D) \leq \rho(DPK_{n,m,\kappa})$

$m \equiv (n^2-2n-1) \pmod{\kappa}$ かつ特定の条件を満たすとき、等号が成立するのは $D = DPK_{n,m,\kappa}$ の場合に限る。

具体的な界限

系 3.3：適切な条件下で、 $\rho(D) \leq \frac{n}{\kappa} + 2 - \frac{1}{\kappa} - \frac{\kappa-1}{n-1} - \frac{m^*}{\kappa(n-1)}$

ここで $m^*$ は $m^* \geq m$ かつ $m^* \equiv (n^2-2n-1) \pmod{\kappa}$ を満たす最小の整数である。

オイラー有向グラフの結果

定理 4.3： $D$ を位数 $n$ 、サイズ少なくとも $2m_0$ の $\kappa$ -連結オイラー有向グラフとする。このとき $\rho(D) \leq \frac{n}{2\kappa} + 2 - \frac{1}{\kappa} - \frac{\kappa-1}{n-1} - \frac{m_0}{\kappa(n-1)}$