일반화된 피터슨 그래프

그래프 이론에서 일반화된 피터슨 그래프는 일반 폴리곤의 정점을 별 폴리곤의 해당 정점에 연결함으로써 형성된 입방형 그래프 계열이다.그들은 피터슨 그래프를 포함하고 피터슨 그래프를 구성하는 방법 중 하나를 일반화한다.일반화된 피터슨 그래프 계열은 1950년 H. S. M. Coxeter에^[1] 의해 도입되었고 1969년 마크 왓킨스에 의해 그 이름이 붙여졌다.^[2]

정의 및 표기법

Watkins의 표기법에서 G(n, k)는 꼭지점이 설정된 그래프다.

${\displaystyle \{u_{0},u_{1},\ldots,u_{n-1},v_{0},v_{1},\ldots,v_{n-1}\}}}}$

엣지 세트

${\displaystyle \{u_{i}u_{i+1}u_{i+1},u_{i}v_{i}v_{i+k}\mid 0\leq i\leq n-1\}}}}$

여기서 첨자는 modulo n과 k < n/2를 읽어야 한다.일부 저자는 GPG(n, k)라는 표기법을 사용한다.동일한 그래프에 대한 Coxeter의 표기법은 {n} + {n/k로, 그래프가 형성되는 일반 n곤과 별 다각형에 대한 Schléfli 기호의 조합이다.피터슨 그래프 자체는 G(5, 2) 또는 {5} + {5/2}이다.

일반화된 Petersen 그래프는 정점 2개, 자체 루프 2개 및 다른 에지 1개가 있는 전압 그래프에서 구성할 수도 있다.^[3]

예

일반화된 피터슨 그래프로는 n-prism G(n, 1)와 Dürer 그래프 G(6, 2), Möbius-Kantor 그래프 G(8, 3)와 도데카헤드론 G(10, 2), 데스아게스 그래프 G(10, 3)와 나우루 그래프 G(12, 5)가 있다.

3-프리즘, 5-프리즘, 뒤러 그래프, G(7, 2) 등 4개의 일반화된 피터슨 그래프는 입방형, 3-Vertex 연결형, 잘 가려진 7개의 그래프(모든 최대 독립 집합의 크기가 동일하다는 의미)^[4]에 속한다.

특성.

이 그래프 계열은 여러 가지 흥미로운 특성을 가지고 있다.예를 들면 다음과 같다.

• G(n, k)는 (n, k) = (10, 2) 또는 k² mod ±1 (mod n)인 경우에만 정점 변환(다른 정점으로 정점을 가져가는 대칭을 가지고 있다는 의미)이다.

• G(n, k)는 엣지 변환(다른 가장자리까지 가는 대칭)으로, (n, k) = (4, 1), (5, 2), (8, 3) (10, 3), (10, 3), (12, 5), (24, 5)의 7가지 경우에 한한다.^[5]따라서 이 7개의 그래프는 유일한 대칭 일반화된 피터슨 그래프다.

• G(n, k)는 n이 짝수이고 k가 홀수인 경우에만 양수적이다.

• G(n, k)는 k² ≡ 1 (mod n)인 경우에만 Cayley 그래프다.

• G(n, k)는 n이 5 modulo 6과 k = 2, n - 2 또는 (n ± 1)/2에 합치될 때(이 네 가지 k의 선택은 이형성 그래프로 이어진다).또한 n이 4로 분할되고, 적어도 8과 같으며, k = n/2가 될 때 해밀턴이 아니다.다른 모든 경우에 그것은 해밀턴의 순환을 가지고 있다.^[6]n이 3 modulo 6 G(n, 2)에 일치할 때 정확히 3개의 해밀턴 사이클을 가진다.^[7]G(n, 2)의 경우 해밀턴 주기 횟수는 n modulo 6의 조합 등급에 따라 달라지며 피보나치 숫자를 포함하는 공식으로 계산할 수 있다.^[8]

• 모든 일반화된 피터슨 그래프는 단위 거리 그래프다.^[9]

이소모르프스

G(n, k)는 k=l 또는 kl ≡ ±1 (mod n)인 경우에만 G(n, l)와 이형이다.^[10]

둘레

G(n, k)의 둘레는 최소 3이고, 특히 최대 8이다.^[11]

${\displaystyle g(n,k)\leq \min \leq \left\{8,k+3,{\frac {n}{\gcd(n,k)}}\오른쪽\}.}$

둘레 값이 정확한 표:

조건	둘레
${\displaystyle n=3k}$	3
$[\displaystyle n=4k}$	4
${\displaystyle k=1}$
${\displaystyle n=5k}$	5
${\displaystyle n=5k/2}$
${\displaystyle k=2}$
${\displaystyle n=6k}$	6
${\displaystyle k=3}$
${\displaystyle n=2k+2}$
${\displaystyle n=7k}$	7
${\displaystyle n=7k/2}$
${\displaystyle n=7k/3}$
${\displaystyle k=4}$
${\displaystyle n=2k+3}$
${\displaystyle n=3k\pm 2}$
그렇지 않으면	8

색수 및 색지수

브룩스의 정리에 따르면 규칙적이기 때문에 그들의 색수는 그들의 정도보다 클 수 없다.일반화된 Petersen 그래프는 세제곱이므로 색도 수는 2 또는 3이 될 수 있다.더 정확히 말하자면:

${\displaystyle \chi(G(n,k))={\begin{case}2&2\mid n\land 2\nmid k\3&2\nmid n\lor 2\mid k\\\end{case}}}}}$

여기서 $\wedge {\displaystyle }$ ${\displaystyle \land}$은(는) 논리적 AND를 나타내고$$, $\vee {\displaystyle }$ ${\displaystyle \lor}$은(는) 논리적 OR을 나타낸다.예를 들어 $G{\displaystyle }$( 5,${\displaystyle 2}$) ${\displaystyle$ G $(5,2)}$의 색수는 3이다$$.

• 

  Petersen 그래프 또는 $G{\displaystyle (}$5${\displaystyle ,}$ 2)의 3가지 색상. ${\displaystyle$ G$(5,2)}$

• 

  Desargues $그래프{\displaystyle }$ ${\displaystyle \mathrm{또는}}$ G${\displaystyle (}$10${\displaystyle ,}$ ${\displaystyle 3}$)의 2-색상. ${\displaystyle$ G($10,3)}$

• 

  뒤러 그래프 또는 $G{\displaystyle }$(6,${\displaystyle }$2${\displaystyle }$)의 3가지 색상. ${\displaystyle$ G$(6,2)}$

Petersen graph는 snark로서 색지수 4를 가지고 있다.다른 모든 일반화된 피터슨 그래프에는 색지수 3이 있다.^[12]

일반화된 피터슨 그래프 G(9, 2)는 3-엣지 색상이 하나만 있는 것으로 알려진 몇 안 되는 그래프 중 하나이다.^[13]

• 

  Petersen 그래프 또는 $G{\displaystyle (}$5${\displaystyle ,}$ ${\displaystyle 2}$ )의 4-엣지 색상 ${\displaystyle$ G$(5,2)}$

• 

  뒤러 그래프 또는 $G{\displaystyle (}$6${\displaystyle ,}$ ${\displaystyle 2}$)의 3-엣지 색상 $[\displaystyle$ G($6,2)}$

• 

  도데카헤드론 또는 $G{\displaystyle (10,}$ ${\displaystyle 2}$)의 3-엣지 색상 $[\displaystyle$ G$(10,2)}$

• 

  Descarges 그래프 $또는{\displaystyle }$G(${\displaystyle 10,3}$ )의 3-엣지 색상 $[\displaystyle$ G($10,3)}$

• 

  Nauru 그래프 $또는{\displaystyle }$G(${\displaystyle 12,5}$ )의 3-엣지 색상 $[\displaystyle$ G$(12,5)}$

피터슨 그래프 자체는 3-엣지 색상이 불가능한 피터슨 그래프 중 유일하게 일반화된 것이다.^[14]

참조