2025-11-17T18:31:12.470972

Distance mutual-visibility coloring: relations with (total) domination, exact distance graphs and graph products

Babu, Brešar, S et al.
The concept of mutual-visibility (MV) has been extended in several directions. A vertex subset $S$ of a graph $G$ is a $k$-distance mutual-visibility ($k$DMV) set if for any two vertices in $S$, there is a geodesic between them of length at most $k$ whose internal vertices are not in $S$. In this paper, we combine this with the MV coloring as follows. For any integer $k\geq1$, a $k$DMV coloring of $G$ is a partition of $V(G)$ into $k$DMV sets, and the $k$DMV chromatic number $χ_{μ_k}(G)$ is the minimum cardinality of such a partition. When $k=1$ or $k\ge {\rm diam}(G)$, it equals the clique cover number $θ(G)$ or the MV chromatic number $χ_μ(G)$, respectively. So, our attention is given to $1<k<{\rm diam}(G)$ with $k=2$ producing the most interesting results. We prove that $χ_{μ_2}(G)\le|V(G)|/2$ and present large families of graphs that attain the bound. In addition, $χ_{μ_2}(G)$ is bounded from above by the total domination number $γ_t(G)$ if $G$ is isolate-free, while in graphs $G$ with girth $g(G)\geq7$, $χ_{μ_2}(G)$ is bounded from below by the domination number $γ(G)$. A surprising relation with the exact distance-2 graphs is found, which results in $θ(G^{[\natural2]})=γ_{t}(G)$ for any isolate-free graph $G$ with $g(G)\geq7$. The relation is explored further in lexicographic product graphs, where we prove the sharp inequalities $χ_{μ_{2}}(G\circ H)\leq θ(G^{[\natural2]})\leq θ\big{(}(G\circ H)^{[\natural2]}\big{)}$. We also prove a sharp lower (resp. upper) bound on $χ_{μ_2}$ (resp. $χ_{μ_k}$) for the Cartesian (resp. strong) product of two connected graphs and show that they are widely sharp. Finally, we characterize the block graphs $G$ with $χ_{μ_k}(G)=χ_μ(G)$, where $k={\rm diam}(G)-1$.
academic

거리 상호가시성 착색: (전체) 지배, 정확 거리 그래프 및 그래프 곱과의 관계

기본 정보

  • 논문 ID: 2510.10284
  • 제목: Distance mutual-visibility coloring: relations with (total) domination, exact distance graphs and graph products
  • 저자: Saneesh Babu, Boštjan Brešar, Aparna Lakshmanan S, Babak Samadi
  • 분류: math.CO (조합론)
  • 발표 시간: 2025년 10월 11일
  • 논문 링크: https://arxiv.org/abs/2510.10284

초록

본 논문은 k-거리 상호가시성 착색 문제를 연구하며, 이는 Di Stefano가 2022년에 도입한 상호가시성 개념의 확장이다. 그래프 G의 정점 부분집합 S에 대해, S의 임의의 두 정점 사이에 길이가 최대 k인 측지선이 존재하고 그 내부 정점이 S에 포함되지 않으면, S를 k-거리 상호가시성 집합(k-DMV 집합)이라 한다. 논문은 이 개념을 상호가시성 착색과 결합하여 k-DMV 착색수 χ_μ_k(G)를 정의한다. k=2일 때 가장 흥미로운 결과가 나타남을 보이며, χ_μ_2(G) ≤ |V(G)|/2를 증명하고 지배수, 전체 지배수 및 정확 거리 그래프와의 깊은 연관성을 확립한다.

연구 배경 및 동기

  1. 문제의 기원: 상호가시성 개념은 원래 Di Stefano가 2022년에 제시했으며, 고전적인 "세 점이 일직선상에 있지 않음" 문제 및 평면 이동 로봇 재배치 문제와 관련이 있다.
  2. 연구 동기:
    • 상호가시성 개념은 새로운 개념이지만 광범위한 관심을 받고 있음(MathSciNet에서 20회 이상 인용)
    • 기존 연구는 주로 상호가시성 집합의 최대 크기에 초점을 맞추고 있으며, 착색 문제에 대한 체계적 연구가 부족함
    • k-거리 제한은 더 효율적인 통신을 가능하게 하며 실제 응용 가치가 있음
  3. 실제 의의: 컴퓨터 네트워크 또는 소셜 네트워크에서, 상호가시성 성질을 가진 정점은 효율적이고 기밀 통신이 필요한 실체를 나타낼 수 있으며, 메시지가 다른 실체를 거치지 않도록 보장한다.

핵심 기여

  1. 새로운 개념 도입: k-거리 상호가시성 착색수 χ_μ_k(G)를 처음으로 정의하여 클리크 커버 수(k=1)와 상호가시성 착색수(k≥diam(G))를 통합함
  2. 기본 경계 확립:
    • χ_μ_2(G) ≤ ⌈|V(G)|/2⌉를 증명하고 이 경계에 도달하는 그래프 족을 제시
    • 고립점이 없는 그래프에 대해 χ_μ_2(G) ≤ γ_t(G)
    • 둘레가 최소 7 이상인 그래프에 대해 χ_μ_2(G) ≥ γ(G)
  3. 정확 거리 그래프와의 연관성 발견: 고립점이 없고 둘레가 최소 7 이상인 그래프 G에 대해 θ(G♮2) = γ_t(G)임을 증명
  4. 그래프 곱의 체계적 연구:
    • 사전식 곱: χ_μ_2(G∘H) ≤ θ(G♮2) ≤ θ((G∘H)♮2)
    • 강 곱: χ_μ_k(G⊠H) ≤ χ_μ_k(G)χ_μ_k(H)
    • 데카르트 곱: χ_μ_2(G□H) ≥ max{χ_μ_2(G)ρ_2(H), χ_μ_2(H)ρ_2(G)}
  5. 특수 그래프 클래스의 특성화: χ_μ_k(G) = χ_μ(G)(여기서 k = diam(G)-1)를 만족하는 블록 그래프를 완전히 특성화

방법론 상세 설명

작업 정의

그래프 G와 양의 정수 k가 주어졌을 때, k-거리 상호가시성 착색은 V(G)를 여러 k-DMV 집합으로 분할하는 착색 방식이다. 여기서 k-DMV 집합 M은 다음을 만족한다: M의 임의의 두 정점 u, v에 대해, 길이가 최대 k인 u, v-측지선이 존재하고 그 내부 정점이 M에 포함되지 않는다.

입력: 그래프 G = (V,E), 양의 정수 k 출력: V(G)의 분할 {S_1, S_2, ..., S_t}로서 각 S_i는 k-DMV 집합 목표: 분할의 집합 개수 t를 최소화

핵심 기술 방법

1. 기초 이론 수립

관찰 1: 직경이 d인 그래프 G에 대해 단조성 체인이 성립: χ_μ(G) = χ_μ_d(G) ≤ χ_μ_(G) ≤ ... ≤ χ_μ_1(G) = θ(G)

관찰 2: 기본 하한 χ_μ_k(G) ≥ ⌈|V(G)|/μ_k(G)⌉

2. k=2 경우의 심층 분석

정리 4: 임의의 연결 그래프 G에 대해 χ_μ_2(G) ≤ ⌈n/2⌉

증명 개요: 생성 트리에 대한 귀납적 구성을 통해 트리를 두 가지 색으로 착색할 수 있는 구조로 분해한다.

정리 5: G가 고립점이 없으면 χ_μ_2(G) ≤ γ_t(G)

증명 방법: 구성적 증명으로서, 전체 지배 집합 D = {v_1,...,v_γ_t(G)}를 이용하여 D_i = N_G(v_i)\⋃_^{i-1}N_G(v_j)를 정의하고 각 D_i가 2DMV 집합임을 증명한다.

3. 둘레와 지배수의 관계

보조정리 6: g(G) ≥ 7이면 χ_μ_2(G)-착색의 각 색 클래스 C는 어떤 정점의 폐쇄 이웃의 부분집합이다.

정리 7: g(G) ≥ 7이면 χ_μ_2(G) ≥ γ(G)

기술적 혁신점

  1. 통합 프레임워크: 클리크 커버, 상호가시성 착색을 k-DMV 착색 프레임워크로 통합
  2. 둘레 조건의 정확한 특성화: 둘레 7이 χ_μ_2(G) ≥ γ(G)를 보장하는 최소값임을 증명
  3. 정확 거리 그래프 연관성: 2DMV 착색과 정확 거리-2 그래프 간의 깊은 연관성을 처음으로 확립
  4. 그래프 곱의 체계적 분석: 세 가지 주요 그래프 곱에 대해 긴밀한 상한과 하한을 제시

실험 설정

이론적 검증 방법

본 논문은 주로 이론적 증명 방법을 채택하며, 구체적인 그래프 족을 구성하여 경계의 긴밀성을 검증한다:

  1. 경로와 순환: P_n과 C_n의 정확한 χ_μ_k 값을 계산
  2. 특수 그래프 족: 다양한 경계에 도달하는 그래프 족을 구성
  3. 곱 그래프: P_n⊠K_m 등 구체적인 곱 그래프의 성질을 분석

핵심 사례 분석

명제 2:

  • 경로 P_n에 대해: χ_μ_k(P_n) = ⌈n/2⌉
  • 순환 C_n에 대해: χ_μ_k(C_n) = ⌈n/3⌉ (n ≤ 3k일 때), ⌈n/2⌉ (그 외)

명제 12: P_n⊠K_m (n≥4, m≥2, k∈{2,...,n-2})에 대해: χ_μ_k(P_n⊠K_m) = 2⌊n/(k+2)⌋ + correction_term

실험 결과

주요 이론적 결과

  1. 기본 경계의 긴밀성:
    • χ_μ_2(G) ≤ ⌈|V(G)|/2⌉는 모든 그래프에 성립하며, 경로와 긴 순환 등에 의해 달성됨
    • χ_μ_2(G) ≤ γ_t(G)는 고립점이 없는 그래프에 성립하며, 차이를 임의로 크게 만드는 그래프 족을 구성할 수 있음
  2. 둘레 조건의 최적성:
    • 둘레가 6이지만 γ(G) = 5 > χ_μ_2(G) = 3인 반례를 구성
    • 둘레 7이 χ_μ_2(G) ≥ γ(G)를 보장하는 최소 조건임을 증명
  3. 그래프 곱 결과의 예리함:
    • 강 곱 경계 χ_μ_k(G⊠H) ≤ χ_μ_k(G)χ_μ_k(H)는 무한 그래프 족에 의해 달성됨
    • 데카르트 곱 하한은 환면 그래프 등에 의해 달성됨

정확 거리 그래프의 놀라운 연관성

정리 8: G가 고립점이 없고 g(G) ≥ 7이면 θ(G♮2) = χ_i_μ_2(G) = γ_t(G)

이 결과는 서로 무관해 보이는 세 개의 그래프 매개변수 사이의 등식 관계를 확립하며, 중요한 이론적 의의를 가진다.

초입방체의 특수성

명제 16: n-초입방체 Q_n에 대해 χ_μ_2(Q_n) ≤ γ(Q_n)

추측: 모든 n에 대해 χ_μ_2(Q_n) = γ(Q_n)

관련 연구

  1. 상호가시성 연구: Di Stefano (2022)가 기본 개념을 도입, Cera 등이 k-거리 버전으로 확장
  2. 상호가시성 착색: Klavžar 등(2025)이 상호가시성 착색 문제를 처음 연구
  3. 정확 거리 그래프: 1980년대에 도입되었으며 최근 다시 주목받고 있음
  4. 지배 이론: 고전적 그래프 이론 연구 분야로서 본 논문과 새로운 연관성을 확립

결론 및 논의

주요 결론

  1. k-거리 상호가시성 착색은 그래프의 구조적 성질을 연구하기 위한 새로운 관점을 제공한다
  2. k=2 경우는 지배 이론 및 정확 거리 그래프와의 깊은 연관성을 보여준다
  3. 서로 다른 그래프 곱 하에서의 행동은 이 매개변수의 본질적 특징을 드러낸다
  4. 둘레 조건은 매개변수 경계를 결정하는 데 핵심적 역할을 한다

한계점

  1. 주요 결과가 k=2 경우에 집중되어 있으며, 일반적 k 값에 대한 연구가 부족함
  2. 일부 경계의 긴밀성은 특정 그래프 족에서만 검증됨
  3. 계산 복잡성 문제는 다루지 않음

향후 연구 방향

논문은 세 가지 구체적인 미해결 문제를 제시한다:

문제 1: χ_μ_2(G) = θ(G)를 만족하는 블록 그래프 G를 특성화하라

문제 2: 연결 그래프 G, H에 대해 χ_μ_2(G□H) ≥ max{χ_μ_2(G)γ(H), χ_μ_2(H)γ(G)}가 성립하는가?

문제 3: 모든 초입방체에 대해 χ_μ_2(Q_n) = γ(Q_n)이 성립하는가?

심층 평가

장점

  1. 이론적 깊이: 그래프 이론의 여러 분야 간 새로운 연관성을 확립하며, 특히 지배 이론 및 정확 거리 그래프와의 관계가 주목할 만함
  2. 결과의 완전성: 많은 긴밀한 상한과 하한을 제공하며, 경계에 도달하는 그래프 족을 구성함
  3. 기술적 혁신: 둘레 조건의 정확한 특성화와 그래프 곱의 체계적 분석은 높은 수준의 기법을 보여줌
  4. 명확한 서술: 정의가 명확하고 증명이 엄밀하며 구조가 합리적임

부족한 점

  1. 계산 복잡성 부재: χ_μ_k(G)의 계산 복잡성을 논의하지 않음
  2. 응용의 한계: 네트워크 통신 응용을 언급했으나 구체적인 응용 시나리오 분석이 부족함
  3. 알고리즘 설계: χ_μ_k(G)를 계산하거나 근사하는 효율적인 알고리즘이 없음

영향력

  1. 이론적 기여: 그래프 이론 연구에 새로운 방향을 개척하며 후속 연구를 촉발할 것으로 예상됨
  2. 기술적 가치: 증명 기법과 구성 방법은 관련 연구에 참고 가치가 있음
  3. 학제간 잠재력: 지배 이론과의 연관성은 두 분야의 교차 발전을 촉진할 수 있음

적용 분야

  1. 네트워크 설계: 통신 경로의 기밀성을 보장해야 하는 네트워크에 응용
  2. 그래프 이론 연구: 그래프 구조적 성질을 연구하기 위한 새로운 도구
  3. 조합 최적화: 관련 최적화 문제에 이론적 기초 제공

참고문헌

논문은 18편의 관련 문헌을 인용하며, 주요 내용은 다음과 같다:

  • Di Stefano (2022): 상호가시성 개념의 원본 문헌
  • Cera 등: k-거리 상호가시성의 확장
  • Klavžar 등: 상호가시성 착색의 첫 연구
  • 고전 그래프 이론 교과서 및 지배 이론 문헌

종합 평가: 이는 상호가시성이라는 신흥 연구 방향에서 중요한 기여를 한 고품질의 이론 그래프 이론 논문이다. 논문은 완전한 이론적 프레임워크를 수립할 뿐만 아니라 고전 그래프 이론 개념과의 깊은 연관성을 발견하여 해당 분야의 발전을 위한 견고한 기초를 마련했다. 응용 및 알고리즘 측면에서는 추가 연구가 필요하지만, 그 이론적 가치와 혁신성으로 인해 해당 분야의 중요한 문헌이 되었다.