2025-11-23T03:01:16.593819

Determining the b-chromatic number of subdivision-vertex neighbourhood coronas

Falcón, Venkatachalam, Margaret
Let $G$ and $H$ be two graphs, each one of them being a path, a cycle or a star. In this paper, we determine the $b$-chromatic number of every subdivision-vertex neighbourhood corona $G\boxdot H$ or $G\boxdot K_n$, where $K_n$ is the complete graph of order $n$. It is also established for those graphs $K_n\boxdot G$ having $m$-degree not greater than $n+2$. All the proofs are accompanied by illustrative examples.
academic

세분화-정점 이웃 코로나의 b-색수 결정

기본 정보

  • 논문 ID: 2302.13667
  • 제목: Determining the b-chromatic number of subdivision-vertex neighbourhood coronas
  • 저자: Raúl M. Falcón (Universidad de Sevilla, Spain), M. Venkatachalam, S. Julie Margaret (Kongunadu Arts and Science College, India)
  • 분류: math.CO (조합론)
  • 발표 시간: 2023년 2월 27일
  • 논문 링크: https://arxiv.org/abs/2302.13667

초록

GG와 HH를 각각 경로, 순환 또는 별 그래프인 두 개의 그래프라고 하자. 본 논문은 각 세분화-정점 이웃 코로나 그래프 G⊡HG\boxdot H 또는 G⊡KnG\boxdot K_n의 b-색수를 결정하며, 여기서 KnK_n은 nn차 완전 그래프이다. mm-차수가 n+2n+2를 초과하지 않는 그래프 Kn⊡GK_n\boxdot G에 대해서도 해당 결과를 확립한다. 모든 증명에는 설명적인 예시가 포함되어 있다.

연구 배경 및 동기

문제 배경

  1. b-색수 개념: Irving과 Manlove가 1999년에 그래프의 b-색 칠하기 개념을 도입했으며, 이는 특수한 정상 kk-칠하기로서 각 색상이 b-정점(다른 모든 색상의 정점과 인접한 정점)을 가져야 한다는 요구사항이 있다.
  2. 계산 복잡성: 그래프의 b-색수를 결정하는 것은 일반적인 경우 NP-어려운 문제이지만, 트리의 경우 다항식 시간에 해결 가능하다.
  3. 그래프 곱 연구: 데카르트 곱, 직접곱, 강곱, 사전식 곱 등 다양한 그래프 곱의 b-색수에 관한 광범위한 연구가 있다.

연구 동기

  1. 이론 완성: 세분화-정점 이웃 코로나(SVN corona)는 중요한 그래프 구성 방법이지만, 그 b-색수 연구는 상대적으로 부족하다.
  2. 방법 체계화: 기본 그래프 클래스(경로, 순환, 별 그래프, 완전 그래프)의 SVN 코로나 그래프의 b-색수를 체계적으로 연구할 필요가 있다.
  3. 응용 가치: b-색수는 네트워크 칠하기, 주파수 할당 등 실제 문제에서 중요한 응용을 가진다.

핵심 기여

  1. 기본 그래프 클래스의 SVN 코로나 b-색수 완전 결정: 경로 PnP_n, 순환 CnC_n, 별 그래프 SnS_n과 경로, 순환, 별 그래프, 완전 그래프의 SVN 코로나에 대해 정확한 b-색수 공식을 제시한다.
  2. 완전 그래프 SVN 코로나의 부분 결과 확립: mm-차수가 n+2n+2 이하인 Kn⊡GK_n\boxdot G에 대해 b-색수를 결정한다.
  3. 구성적 증명 방법 제공: 모든 결과는 구체적인 최적 b-색 칠하기를 구성하여 증명되며, 상세한 그래프 예시가 포함된다.
  4. 체계적 분석 프레임워크 개발: SVN 코로나 그래프의 b-색수를 분석하기 위한 일반적인 방법과 기술 도구를 확립한다.

방법 상세 설명

작업 정의

입력: 두 그래프 GG와 HH, 여기서 G,H∈{Pn,Cn,Sn,Kn}G,H \in \{P_n, C_n, S_n, K_n\}출력: SVN 코로나 그래프 G⊡HG\boxdot H의 b-색수 φ(G⊡H)\varphi(G\boxdot H)제약: Kn⊡GK_n\boxdot G의 경우, m(Kn⊡G)≤n+2m(K_n\boxdot G) \leq n+2를 요구한다.

SVN 코로나 그래프 구성

주어진 그래프 GG와 HH에 대해 SVN 코로나 그래프 G⊡HG\boxdot H의 구성 과정:

  1. 그래프 GG의 세분화 그래프 S(G)S(G)에서 시작한다(각 간선에 새로운 정점 삽입).
  2. ∣V(G)∣|V(G)|개의 HH의 정점 분리 복사본을 추가한다.
  3. S(G)S(G)의 각 원래 정점 uiu_i의 이웃에 있는 모든 정점을 (i+1)(i+1)번째 HH 복사본의 모든 정점에 연결한다.

핵심 기술 도구

1. m-차수 개념

nn차 그래프 GG에 대해, 그 m-차수는 다음과 같이 정의된다: m(G):=∣{i∈{1,…,n}:d(vi−1)≥i−1}∣m(G) := |\{i \in \{1,\ldots,n\} : d(v_{i-1}) \geq i-1\}| 여기서 정점은 차수의 비증가 순서로 정렬된다.

2. 기본 경계

  • 하한: χ(G)≤φ(G)\chi(G) \leq \varphi(G) (색수는 b-색수를 초과하지 않음)
  • 상한: φ(G)≤Δ(G)+1\varphi(G) \leq \Delta(G) + 1 (b-색수는 최대 차수 더하기 1을 초과하지 않음)
  • m-차수 경계: φ(G)≤m(G)\varphi(G) \leq m(G)

3. SVN 코로나 그래프의 차수 공식

G⊡HG\boxdot H의 정점 vv에 대해:

d_G(v), & \text{if } v \in V(G) \\ 2|V(H)| + 2, & \text{if } v \in I(G) \\ d_G(u_i) + d_H(v_j), & \text{if } v = v_{i,j} \end{cases}$$ ### 분석 전략 논문은 분류 토론 방법을 채택하여 다양한 그래프 클래스 조합에 대해: 1. **경로의 SVN 코로나**(제3절) 2. **순환의 SVN 코로나**(제4절) 3. **별 그래프의 SVN 코로나**(제5절) 4. **완전 그래프의 SVN 코로나**(제6절) 각 경우는 구체적인 b-색 칠하기를 구성하여 상한의 타이트함을 증명한다. ## 주요 결과 ### 경로 SVN 코로나의 b-색수 **정리 6** ($P_n \boxdot P_t$): $$\varphi(P_n \boxdot P_t) = \begin{cases} 4, & \text{if } n=3 \text{ and } t \in \{3,4\} \\ 5, & \text{if } (n=3 \text{ and } t \geq 5) \text{ or } n \in \{4,5\} \\ n-1, & \text{if } 6 \leq n \leq 2t+3 \\ 2t+3, & \text{otherwise} \end{cases}$$ **정리 7-9**: 유사하게 $P_n \boxdot C_t$, $P_n \boxdot S_t$, $P_n \boxdot K_t$의 정확한 공식을 제시한다. ### 순환 SVN 코로나의 b-색수 **정리 11** ($C_n \boxdot P_t$): $$\varphi(C_n \boxdot P_t) = \begin{cases} 5, & \text{if } n \in \{3,4\} \\ n, & \text{if } 5 \leq n \leq 2t+2 \\ 2t+3, & \text{otherwise} \end{cases}$$ ### 별 그래프 SVN 코로나의 b-색수 **정리 17**: 별 그래프와 기본 그래프 클래스의 SVN 코로나에 대해 완전한 b-색수 공식을 확립하며, 주요 결과는 다음을 포함한다: $$\varphi(S_n \boxdot K_{t'}) = \min\{n, t'+2\} + t'$$ ### 완전 그래프 SVN 코로나의 b-색수 **정리 20-24**: m-차수 제약 조건 하에서 $K_n\boxdot G$의 b-색수를 제시한다. 예를 들어: $$\varphi(K_n \boxdot P_t) = \begin{cases} n+1, & \text{특정 조건} \\ n+2, & \text{다른 조건} \end{cases}$$ ## 기술적 혁신점 ### 1. 구성적 증명 방법 - 상한을 증명할 뿐만 아니라 명시적 구성을 통해 최적 b-색 칠하기로 하한을 증명한다. - 각 구성에는 상세한 그래프 예시가 포함되어 결과의 검증 가능성을 높인다. ### 2. b-무지개 집합 개념 b-정점 식별을 단순화하기 위해 b-무지개 집합 개념을 도입하며, 그래프에서 다양한 기호로 표시한다: - 십자 기호 ×: 특정 b-무지개 집합의 정점 - 삼각형 △: 기타 b-정점 - 원 ●: 일반 정점 ### 3. 모듈로 연산 기법 칠하기 구성에서 모듈로 연산을 광범위하게 사용하여 칠하기의 주기성과 정확성을 보장한다. 예를 들어: $$c(u_i) = (i+1) \bmod \min\{m(P_n \boxdot P_t), n\}$$ ### 4. 분류 토론의 체계화 매개변수 범위에 따라 세밀한 분류 토론을 수행하여 모든 가능한 경우를 포함한다. ## 실험 검증 ### 그래프 검증 논문은 이론적 결과를 검증하기 위해 많은 그래프 예시를 제공한다: - 그림 2: $P_{10} \boxdot P_3$의 최적 b-색 칠하기 - 그림 3-4: 다양한 매개변수 하의 경로 SVN 코로나 칠하기 - 그림 11: 순환 SVN 코로나 칠하기 예시 - 그림 17-18: 별 그래프 SVN 코로나 칠하기 구성 ### 구성 검증 각 정리의 증명에는 구체적인 칠하기 구성 알고리즘이 포함되어 직접 검증할 수 있다: 1. 칠하기의 정확성 (인접 정점은 다른 색) 2. b-정점의 존재성 (각 색상은 b-정점을 가짐) 3. 최적성 (이론적 상한 달성) ## 관련 연구 ### b-색수 연구 역사 1. **Irving-Manlove (1999)**: b-색수 개념의 최초 도입 2. **다양한 그래프 곱 연구**: 데카르트 곱, 직접곱, 강곱 등의 b-색수는 이미 광범위하게 연구됨 3. **특수 그래프 클래스**: 경로, 순환, 별 그래프, 완전 그래프의 b-색수는 알려짐 ### 본 논문의 위치 - **공백 채우기**: SVN 코로나 그래프의 b-색수 연구는 상대적으로 부족함 - **방법 혁신**: 체계적인 구성 방법 제공 - **결과 완전성**: 기본 그래프 클래스 조합의 완전한 결과 제시 ## 결론 및 토론 ### 주요 결론 1. **완전성**: 기본 그래프 클래스(경로, 순환, 별 그래프, 완전 그래프)의 SVN 코로나에 대해 완전한 b-색수 결정 결과를 제시한다. 2. **정확성**: 모든 결과는 근사값이나 경계가 아닌 정확한 값이다. 3. **구성성**: 구체적인 최적 칠하기 구성 방법을 제공한다. ### 제한사항 1. **그래프 클래스 제한**: 기본 그래프 클래스만 고려하며, 일반 그래프에 대한 결과는 추가 연구가 필요하다. 2. **완전 그래프 제약**: $K_n\boxdot G$의 결과는 m-차수 제약 조건이 필요하다. 3. **복잡성**: 일부 경우의 분류 토론이 상당히 복잡하다. ### 향후 방향 1. **그래프 클래스 확장**: 더 일반적인 그래프 클래스의 SVN 코로나 b-색수 연구 2. **알고리즘 연구**: 효율적인 b-색수 계산 알고리즘 개발 3. **응용 탐색**: 실제 네트워크 칠하기 문제에 결과 적용 ## 심층 평가 ### 장점 1. **이론적 기여 현저함**: 중요한 그래프 곱 클래스의 b-색수 문제를 체계적으로 해결한다. 2. **방법 엄밀함**: 구성적 증명 방법은 결과의 신뢰성을 보장한다. 3. **표현 명확함**: 많은 그래프 예시와 설명으로 복잡한 증명을 이해하기 쉽게 한다. 4. **결과 완전성**: 기본 그래프 클래스의 모든 중요한 조합을 포함한다. ### 부족한 점 1. **기술적 혁신 제한**: 주로 기존 방법의 체계적 응용이며, 근본적인 새로운 기술이 부족하다. 2. **응용 가치 불명확**: 실제 응용 시나리오에 대한 논의가 부족하다. 3. **계산 복잡도 분석 부재**: 구성 알고리즘의 시간 복잡도가 논의되지 않았다. ### 영향력 1. **이론적 가치**: 그래프의 b-색수 이론에 중요한 보충을 제공한다. 2. **방법적 가치**: 구성 방법은 다른 그래프 곱 연구로 일반화될 수 있다. 3. **완전성 가치**: SVN 코로나 그래프의 b-색수 연구 공백을 채운다. ### 적용 시나리오 1. **이론 연구**: 그래프 이론 및 조합 최적화 분야의 기초 연구 2. **네트워크 설계**: 이웃 제약을 고려해야 하는 네트워크 칠하기 문제 3. **알고리즘 설계**: 더 복잡한 그래프 칠하기 알고리즘의 기초 모듈 ## 참고문헌 논문은 25편의 관련 문헌을 인용하며, 주요 내용은 다음을 포함한다: - Irving & Manlove (1999): b-색수의 원래 정의 - Kouider & Mahéo 등: 다양한 그래프 곱의 b-색수 연구 - Liu & Lu (2013): SVN 코로나 그래프의 스펙트럼 이론 연구 - Brooks (1941): 그래프 칠하기의 고전적 결과