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) 두 개의 서로 다른 $\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)}$