일반화 페테르센 그래프

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요

일반화 페테르센 그래프는 정수 n과 k를 사용하여 정의되는 그래프의 한 종류이다. GPG(n, k)로 표기하며, n이 3 이상이고, k는 n의 배수가 아니며, n이 짝수일 경우 k는 n/2의 배수가 아니어야 한다. 이 그래프는 2n개의 꼭짓점과 3n개의 변을 가지는 삼차 그래프이며, 왓킨스, 콕서터 표기법 등 다양한 방식으로 표현될 수 있다. 일반화 페테르센 그래프는 정점 추이 그래프, 변 추이 그래프, 이분 그래프, 케일리 그래프 등 다양한 성질을 가지며, 해밀턴 순환과 경로, 교차수, 색칠수 등 그래프 이론의 여러 개념과 관련된다. 대표적인 예시로는 페테르센 그래프, 뒤러 그래프, 데자르그 그래프 등이 있으며, 역사적으로 뒤러의 판화, 페테르센, 콕서터, 왓킨스 등에 의해 연구되었다.

일반화 페테르센 그래프

일반 정보

이미지 준비중입니다.

페테르센 그래프의 다이어그램

종류	그래프 이론
꼭짓점	10
변	15
정규성	3-정규 그래프
지름	2
둘레	5
채색수	3
색인	3
대칭성	5
그래프 속성	큐빅 비평면 그래프 비해밀턴 그래프 무어 그래프 스트롱리 레귤러 그래프
군	대칭군 S5

명명법

쇼산 표기법	G(5, 2)

관련 그래프	일반화된 페테르센 그래프 테테르 그래프

2. 정의

3 이상의 정수 $n\ge3$ 과, $n$ 의 배수가 아닌 정수 $k\in\mathbb Z$ , $n\nmid k$ 가 주어졌다고 하자. 또한, 만약 $n$ 이 짝수라면 $n/2\nmid k$ 라고 하자.

일반화 페테르센 그래프 $\operatorname{GPG}(n,k)$ 는 다음과 같은 그래프이다.
: $\operatorname V(\operatorname{GPG}(n,k))=\{u_i,v_i\colon i\in\mathbb Z/n\}$
: $\operatorname E(\operatorname{GPG}(n,k))=\{u_i u_{i+1}, u_i v_i, v_i v_{i+k}\colon i\in\mathbb Z/n\}$
여기서 첨자는 법 $n$ 으로 계산한다. 즉, $u_{n+i}=u_i$ 및 $v_{n+i}=u_i$ 로 간주한다.
일반화 페테르센 그래프의 변 가운데, $u_iv_i$ 꼴의 변을 바큇살(spoke^영어)이라고 한다.

당연히
: $\operatorname{GPG}(n,k)=\operatorname{GPG}(n,k+n)=\operatorname{GPG}(n,-k)$
이므로, 보통
: $1\le k< n/2$
를 가정한다.

왓킨스(Watkins)가 제시한 표기법 G(n, k)는 정점 집합 $\{u_0, u_1, \ldots, u_{n-1}, v_0, v_1, \ldots, v_{n-1}\}$ 과 간선 집합 $\{u_iu_{i+1}, u_iv_i, v_iv_{i+k} \mid 0 \le i \le n-1 \}$ 을 갖는 그래프이다. 여기서 아래첨자는 모듈로 n으로 읽으며, k < n/2이다. 일부 저자는 GPG(n, k) 표기법을 사용한다. 같은 그래프에 대한 콕서터 표기법은 {n} + {n/k}인데, 이 표기법은 그래프가 형성되는 정다각형 및 별 다각형의 슐레플리 기호를 조합한 것이다. 페테르센 그래프 자체는 G(5, 2) 또는 {5} + {5/2}이다.

어떤 일반화된 페테르센 그래프든 두 개의 정점, 두 개의 자기 루프, 그리고 하나의 다른 간선을 가진 전압 그래프로부터 구성될 수도 있다.

2.1. 왓킨스 표기법

왓킨스(Watkins)가 제시한 표기법 G(n, k)는 정점 집합 $\{u_0, u_1, \ldots, u_{n-1}, v_0, v_1, \ldots, v_{n-1}\}$ 과 간선 집합 $\{u_iu_{i+1}, u_iv_i, v_iv_{i+k} \mid 0 \le i \le n-1 \}$ 을 갖는 그래프이다. 여기서 아래첨자는 모듈로 n으로 읽으며, k < n/2이다. 일부 저자는 GPG(n, k) 표기법을 사용한다. 같은 그래프에 대한 콕서터 표기법은 {n} + {n/k}인데, 이 표기법은 그래프가 형성되는 정다각형 및 별 다각형의 슐레플리 기호를 조합한 것이다. 페테르센 그래프 자체는 G(5, 2) 또는 {5} + {5/2}이다.

2.2. 콕서터 표기법

콕서터(Coxeter) 표기법은 {n} + {n/k}이며, 그래프가 형성되는 정다각형 및 별 다각형의 슐레플리 기호를 조합한 것이다. 페테르센 그래프 자체는 G(5, 2) 또는 {5} + {5/2}이다.

Watkins의 표기법에서, G(n, k)는 다음과 같은 정점 집합을 갖는 그래프이다.

: $\{u_0, u_1, \ldots, u_{n-1}, v_0, v_1, \ldots, v_{n-1}\}$

그리고 간선 집합은 다음과 같다.

: $\{u_iu_{i+1}, u_iv_i, v_iv_{i+k} \mid 0 \le i \le n-1 \}$

여기서 아래첨자는 모듈로 n으로 읽으며, k < n/2이다. 일부 저자는 GPG(n, k) 표기법을 사용한다.

어떤 일반화된 페테르센 그래프든 두 개의 정점, 두 개의 자기 루프, 그리고 하나의 다른 간선을 가진 전압 그래프로부터 구성될 수 있다.

2.3. 전압 그래프

Watkins의 표기법에서 G(n, k)는 다음과 같은 정점 집합을 갖는 그래프이다.

:{u₀, u₁, …, u_n-1, v₀, v₁, …, v_n-1}

그리고 간선 집합은 다음과 같다.

:{u_iu_i+1, u_iv_i, v_iv_i+k | 0 ≤ i ≤ n-1}

여기서 아래첨자는 모듈로 n으로 읽으며, k < n/2이다. 일부 저자는 GPG(n, k) 표기법을 사용한다. 같은 그래프에 대한 Coxeter의 표기법은 {n} + {n/k}인데, 이 표기법은 그래프가 형성되는 정다각형 및 별 다각형의 슐레플리 기호를 조합한 것이다. 페테르센 그래프 자체는 G(5, 2) 또는 {5} + {5/2}이다.

어떤 일반화된 페테르센 그래프든 두 개의 정점, 두 개의 자기 루프, 그리고 하나의 다른 간선을 가진 전압 그래프로부터 구성될 수 있다.

3. 성질

* G(n, k)는 정점-추이 그래프이다. 단, (n, k) = (10, 2)이거나 k² ≡ ±1 (mod n)인 경우에만 해당된다.
* G(n, k)는 변-추이 그래프(모든 변을 다른 변으로 옮기는 대칭성을 가짐)는 다음 일곱 가지 경우에만 해당된다: (n, k) = (4, 1), (5, 2), (8, 3), (10, 2), (10, 3), (12, 5), (24, 5). 따라서 이 일곱 개의 그래프는 유일한 대칭 그래프 일반화 페테르센 그래프이다.
* G(n, k)는 n이 짝수이고 k가 홀수인 경우에만 이분 그래프이다.
* G(n, k)는 케일리 그래프이다. 단, k² ≡ 1 (mod n)인 경우에만 해당된다.
* G(n, k)는 n이 6을 법으로 5와 합동이고 k = 2, n − 2 또는 (n ± 1)/2일 때 저해밀턴 그래프이다(이 네 가지 k 선택은 동형 그래프로 이어진다). 또한 n이 4로 나누어지고, 8 이상이며, k = n/2일 때 해밀턴 그래프가 아니다. 다른 모든 경우에는 해밀턴 순환을 갖는다. n이 6을 법으로 3과 합동일 때 G(n, 2)는 정확히 세 개의 해밀턴 순환을 갖는다. G(n, 2)의 경우 해밀턴 순환의 수는 n을 6으로 나눈 나머지에 따라 달라지며 피보나치 수를 포함하는 공식을 사용하여 계산할 수 있다.

G(9, 2)의 세 개의 해밀턴 순환 중 하나. 동일한 그래프의 다른 두 해밀턴 순환은 그림의 40° 회전에 대해 대칭입니다.

* 모든 일반화 페테르센 그래프는 단위 거리 그래프이다.

3.1. 기본 성질

일반화 페테르센 그래프 $\operatorname{GPG}(n,k)$ 는 $2n$ 개의 꼭짓점과 $3n$ 개의 변을 가지는 삼차 그래프이며, 완벽 부합을 갖는다. 구체적으로, $\{u_iv_i\}_{i\in\mathbb Z/n}$ 은 완벽 부합을 이룬다.

페테르센 그래프 \operatorname{GPG}(5,2) 속의 완벽 부합 — 페테르센 그래프 $\operatorname{GPG}(5,2)$ 속의 완벽 부합

일반화 페테르센 그래프는 여러 흥미로운 속성을 가지고 있다.

*

\operatorname{GPG}(n,k)

는 정점-추이 그래프이다. 단,

(n,k) = (10,2)

이거나

k^2 \equiv \pm 1 \pmod n

인 경우에만 해당된다.
*

\operatorname{GPG}(n,k)

는 변-추이 그래프는 다음 일곱 가지 경우에만 해당된다:

(n,k) = (4,1), (5,2), (8,3), (10,2), (10,3), (12,5), (24,5)

. 따라서 이 일곱 개의 그래프는 유일한 대칭 그래프 일반화 페테르센 그래프이다.
*

\operatorname{GPG}(n,k)

는

n

이 짝수이고

k

가 홀수인 경우에만 이분 그래프이다.
*

\operatorname{GPG}(n,k)

는 케일리 그래프이다. 단,

k^2 \equiv 1 \pmod n

인 경우에만 해당된다.
*

\operatorname{GPG}(n,k)

는

n

이 6을 법으로 5와 합동이고

k = 2, n-2

또는

(n \pm 1)/2

일 때 저해밀턴 그래프이다(이 네 가지

k

선택은 동형 그래프로 이어진다). 또한

n

이 4로 나누어지고, 8 이상이며,

k = n/2

일 때 해밀턴 그래프가 아니다. 다른 모든 경우에는 해밀턴 순환을 갖는다.

n

이 6을 법으로 3과 합동일 때

\operatorname{GPG}(n,2)

는 정확히 세 개의 해밀턴 순환을 갖는다.

* 모든 일반화 페테르센 그래프는 단위 거리 그래프이다.

3.2. 동형

임의의 정수 $n\ge3$ 및 정수 $1\le k,k' 에 대하여, 다음 두 조건은 서로 동치 이다.$

* $\operatorname{GPG}(n,k)\cong\operatorname{GPG}(n,k')$
* $kk' \equiv \pm1 \pmod n$

예를 들어, $\operatorname{GPG}(7,2)\cong\operatorname{GPG}(7,3)$ 이다. G(n, k)는 k=l 또는 kl ≡ ±1 (mod n)인 경우에만 G(n, l)과 동형이다.

3.3. 안둘레(Girth)

일반화 페테르센 그래프 $\operatorname{GPG}(n,k)$ 의 안둘레는 항상 $\min\{8,k+3,n/\gcd\{n,k\}\}$ 이하이다. 이는 길이 8의 순환, 길이 $k+3$ 의 순환, 길이 $n/\gcd\{n,k\}$ 의 순환이 존재하기 때문이다.

또한, 다음이 성립한다.

: $\operatorname{girth}(\operatorname{GPG}(ak\pm b,k))\le a+b+2$

이는 길이 $a+b+2$ 의 순환이 존재하기 때문이다.

만약 $1\le k 이며, k=\min\left\{1\le k' 일 때, 일반화 페테르센 그래프 \operatorname{GPG}(n,k) 의 안둘레는 다음 표에서, 위에서부터 가장 먼저 해당하는 행에 의해 주어진다.$

👆

좌우로 밀어서 보기

\| 안둘레
$n=3k$	3
$n=4k$	4
$k=1$	4
$n=5k$	5
$n=5k/2$
$k=2$
$n=6k$	6
$k=3$
$n=2k+2$
$n=7k$	7
$n=7k/2$
$n=7k/3$
$k=4$
$n=2k+3$
$n=3k\pm2$
그 밖의 경우	8

3.4. 케일리 그래프

일반화 페테르센 그래프 $\operatorname{GPG}(n,k)$ 는 특정 조건을 만족할 때 유한군의 케일리 그래프와 동형이다.

다음 두 조건은 서로 동치이다.

* 어떤 유한군의 케일리 그래프와 동형이다.
* $k^2\equiv1\pmod n$

예를 들어, 나우루 그래프 $\operatorname{GPG}(12,5)$ 는 $5^2\equiv 1\pmod{12}$ 를 만족하며, 대칭군 $\operatorname{Sym}(4)$ 의 케일리 그래프이다.

나우루 그래프 \operatorname{GPG}(12,5)는 대칭군 \operatorname{Sym}(4)의 케일리 그래프이다. — 나우루 그래프 $\operatorname{GPG}(12,5)$ 는 대칭군 $\operatorname{Sym}(4)$ 의 케일리 그래프이다.

각기둥 그래프

\operatorname{GPG}(n,1)

는 크기

2n

의 정이면체군

\operatorname{Dih}(n)

의 케일리 그래프이다. 반면, 페테르센 그래프

\operatorname{GPG}(5,2)

는 케일리 그래프가 아니다.

3.5. 꼭짓점 색칠

일반화 페테르센 그래프는 삼차 그래프이므로, 브룩스 정리(Brooks’ theorem)에 의하여 그 색칠수는 2 또는 3이다. 일반화 페테르센 그래프 $\operatorname{GPG}(n,k)$ 에 대하여, 다음 두 조건이 서로 동치이다.

* 이분 그래프이다. (즉, 색칠수가 2이다.)
* $n$ 이 짝수이며, $k$ 는 홀수이다.

다시 말해, 일반화 페테르센 그래프 $\operatorname{GPG}(n,k)$ 의 색칠수는 다음과 같다.

: $\chi(\operatorname{GPG}(n,k))=\begin{cases}2&2\mid n \land 2\nmid k\\3&2\nmid n \lor 2\mid k\end{cases}$

여기서 $\land$ 는 논리곱(AND), $\lor$ 는 논리합(OR)이다. 예를 들어, 페테르센 그래프 $\operatorname{GPG}(5,2)$ 의 색칠수는 3이다.

페테르센 그래프 \operatorname{GPG}(5,2)의 3색 그래프 색칠 — 페테르센 그래프 $\operatorname{GPG}(5,2)$ 의 3색 그래프 색칠

데자르그 그래프 \operatorname{GPG}(10,3)의 2색 그래프 색칠 — 데자르그 그래프 $\operatorname{GPG}(10,3)$ 의 2색 그래프 색칠

뒤러 그래프 \operatorname{GPG}(6,2)의 3색 그래프 색칠 — 뒤러 그래프 $\operatorname{GPG}(6,2)$ 의 3색 그래프 색칠

3.6. 변 색칠

페테르센 그래프의 변 색칠수는 4이다. 페테르센 그래프는 변 색칠수가 4 이상인 가장 작은 삼차 그래프이다. 페테르센 그래프는 스나크이므로 채색 지수는 4이다. 즉, 변에 4가지 색이 필요하다. 반면, 페테르센 그래프가 아닌 다른 모든 일반화 페테르센 그래프의 변 색칠수는 3이다. 이는 비징의 정리에 따른 유일한 가능성이다.

페테르센 그래프 \operatorname{GPG}(5,2)의 4색 변 색칠 — 페테르센 그래프 $\operatorname{GPG}(5,2)$ 의 4색 변 색칠

뒤러 그래프 \operatorname{GPG}(6,2)의 3색 변 색칠 — 뒤러 그래프 $\operatorname{GPG}(6,2)$ 의 3색 변 색칠

정십이면체 그래프 \operatorname{GPG}(10,2)의 3색 변 색칠 — 정십이면체 그래프 $\operatorname{GPG}(10,2)$ 의 3색 변 색칠

데자르그 그래프 \operatorname{GPG}(10,3)의 3색 변 색칠 — 데자르그 그래프 $\operatorname{GPG}(10,3)$ 의 3색 변 색칠

나우루 그래프 \operatorname{GPG}(12,5)의 3색 변 색칠 — 나우루 그래프 $\operatorname{GPG}(12,5)$ 의 3색 변 색칠

일반화 페테르센 그래프

\operatorname{GPG}(9,2)

는 (색들의 순열을 무시하면) 유일한 3색 변 색칠을 갖는다. 페테르센 그래프 자체는 3-변 채색이 불가능한 유일한 일반화 페테르센 그래프이다.

3.7. 해밀턴 경로와 순환

임의의 일반화 페테르센 그래프 $\operatorname{GPG}(n,k)$ ( $3\le n$ , $1\le k)에 대하여, 다음 두 가지 가운데 정확히 하나가 성립한다.$

* (가) 해밀턴 순환을 갖는다.
* (나) $n\equiv5\pmod6$ 이며, $k\in\{2,(n-1)/2\}$ 이다.

또한, (나)의 경우, 임의의 꼭짓점을 제거하면 이는 해밀턴 순환을 갖는다. 특히, 모든 일반화 페테르센 그래프는 항상 해밀턴 경로를 갖는다.

예를 들어, 페테르센 그래프 $\operatorname{GPG}(5,2)$ 는 해밀턴 경로를 가지지만, (나)의 경우에 해당하므로 해밀턴 순환을 가지지 못한다.

뒤러 그래프 \operatorname{GPG}(6,2) 속의 해밀턴 순환. 맨 밖의 변들이 해밀턴 순환을 이룬다. — 뒤러 그래프 $\operatorname{GPG}(6,2)$ 속의 해밀턴 순환. 맨 밖의 변들이 해밀턴 순환을 이룬다.

일반화 페테르센 그래프 \operatorname{GPG}(8,3) 속의 해밀턴 순환. 맨 밖의 변들이 해밀턴 순환을 이룬다. — 일반화 페테르센 그래프 $\operatorname{GPG}(8,3)$ 속의 해밀턴 순환. 맨 밖의 변들이 해밀턴 순환을 이룬다.

일반화 페테르센 그래프 \operatorname{GPG}(9,2) 속의 해밀턴 순환. 해밀턴 순환에 속하는 변들은 굵게 칠해졌다. — 일반화 페테르센 그래프 $\operatorname{GPG}(9,2)$ 속의 해밀턴 순환. 해밀턴 순환에 속하는 변들은 굵게 칠해졌다.

정십이면체 그래프 \operatorname{GPG}(10,2) 속의 해밀턴 순환. 해밀턴 순환에 속하는 변들은 붉은 색으로 굵게 칠해졌다. — 정십이면체 그래프 $\operatorname{GPG}(10,2)$ 속의 해밀턴 순환. 해밀턴 순환에 속하는 변들은 붉은 색으로 굵게 칠해졌다.

나우루 그래프 \operatorname{GPG}(12,5) 속의 해밀턴 순환. 맨 밖의 변들이 해밀턴 순환을 이룬다. — 나우루 그래프 $\operatorname{GPG}(12,5)$ 속의 해밀턴 순환. 맨 밖의 변들이 해밀턴 순환을 이룬다.

\operatorname{GPG}(n,k)

는

n

이 6을 법으로 5와 합동이고

k

= 2,

n

− 2 또는 (

n

± 1)/2일 때 저해밀턴 그래프이다(이 네 가지

k

선택은 동형 그래프로 이어진다). 또한

n

이 4로 나누어지고, 8 이상이며,

k

n

/2일 때 해밀턴 그래프가 아니다. 다른 모든 경우에는 해밀턴 순환을 갖는다.

3.8. 교차수

각기둥 그래프인 일반화 페테르센 그래프 $\operatorname{GPG}(n,1)$ 은 평면 그래프이며, 그래프 교차수는 0이다. 페테르센 그래프 $\operatorname{GPG}(5,2)$ 의 그래프 교차수는 2이고, 나우루 그래프 $\operatorname{GPG}(12,5)$ 의 그래프 교차수는 8이다. 이 두 그래프는 모두 평면 그래프가 아니다.

오각기둥 그래프 \operatorname{GPG}(5,1)의 교차수는 0이다. — 오각기둥 그래프 $\operatorname{GPG}(5,1)$ 의 교차수는 0이다.

페테르센 그래프 \operatorname{GPG}(5,2)의 교차수는 2이다. — 페테르센 그래프 $\operatorname{GPG}(5,2)$ 의 교차수는 2이다.

나우루 그래프 \operatorname{GPG}(12,5)의 교차수는 8이다. — 나우루 그래프 $\operatorname{GPG}(12,5)$ 의 교차수는 8이다.

평면 그래프가 아닌 모든 그래프는 완전 그래프

K_5

또는 완전 이분 그래프

K_{3,3}

를 그래프 마이너로 가지는데, 페테르센 그래프

\operatorname{GPG}(5,2)

는 이 둘 모두를 그래프 마이너로 갖는다.

3.9. 완벽한 색칠 (Perfect Colorings)

일반화 페테르센 그래프 G(n, 2)와 G(n, 3)의 모든 완벽한 2-채색에 대한 허용 행렬은 다음과 같다.

👆

좌우로 밀어서 보기

허용 행렬
	G(n, 2)	G(n, 3)
	모든 그래프	모든 그래프
	단, G(3m, 2)	그래프 없음
	그래프 없음	단, G(2m,3)
	그래프 없음	단, G(4m,3)
	단, G(5m,2)	단, G(5m,3)
	그래프 없음	단, G(2m,3)

4. 예시

일반화 페테르센 그래프 가운데 일부는 다음과 같은 특별한 이름을 갖는다.

* 페테르센 그래프는 일반화 페테르센 그래프 GPG(5, 2)이다. 이는 완전 그래프 K₅의 선 그래프의 여 그래프와 동형이다.
* 뒤러 그래프(Dürer graph^영어)는 일반화 페테르센 그래프 GPG(6,2)이다.
* 일반화 페테르센 그래프 GPG(10,2)는 정십이면체의 꼭짓점 및 변들로 구성된 그래프와 같다.
* 데자르그 그래프(Desargues graph^영어)는 일반화 페테르센 그래프 GPG(10, 3)이다.
* 일반화 페테르센 그래프 GPG(n,1)는 n각형 각기둥의 꼭짓점 및 변들로 구성된 그래프와 같다.

일반화 페테르센 그래프에는 n-각기둥 G(n, 1), 뒤러 그래프 G(6, 2), 뫼비우스-칸토어 그래프 G(8, 3), 정십이면체 G(10, 2), 데자르그 그래프 G(10, 3) 및 나우루 그래프 G(12, 5)가 있다.

세 개의 각기둥, 다섯 개의 각기둥, 뒤러 그래프, 그리고 G(7, 2)를 포함한 네 개의 일반화 페테르센 그래프는 정규 그래프, 3-정점 연결 그래프이며, 모든 극대 독립 집합이 동일한 크기를 갖는 잘 덮인 그래프인 일곱 개의 그래프 중 하나이다.

5. 역사

알브레히트 뒤러의 1514년 판화 《멜란콜리아 1》(Melancholia Ⅰ^독일어)에는 다면체가 등장하는데, 그 꼭짓점과 변으로 구성된 그래프는 뒤러 그래프이다.

1898년에 덴마크의 수학자 율리우스 페테르센은 이 그래프를 다룬 3쪽의 논문을 출판하였으며, 이로부터 명명되었다. 페테르센은 이 그래프를, 임의의 변을 제거하더라도 연결 그래프로 남는 연결 삼차 그래프는 모두 변 색칠수가 3 이하라는 (잘못된) 추측에 대한 반례로 제시하였다.

“데자르그 그래프”라는 이름은 프랑스의 수학자 지라르 데자르그의 이름을 딴 것이다. 데자르그가 연구한 사영기하학의 한 정리에서 등장하는 작도에서, 각 직선과 점에 그래프 꼭짓점을 대응시키고, 서로 인접하는 점과 직선 사이를 변으로 이으면 데자르그 그래프가 된다.

해럴드 스콧 맥도널드 콕서터는 1950년에 일반화 페테르센 그래프를 도입하였다. 콕서터는 일반화 페테르센 그래프 $\operatorname{GPG}(n,k)$ 를 $\{n\}+\{n/k\}$ 로 표기하였으며, 이에 특별한 이름을 부여하지 않았다.

1969년에 마크 왓킨스(Mark E. Watkins^영어)가 이 그래프 족을 “일반화 페테르센 그래프”(generalized Petersen graph^영어)라고 명명하였다.

“나우루 그래프”(Nauru graph^영어)라는 이름은 데이비드 아서 엡스타인(David Arthur Eppstein^영어)이 도입하였으며, 이 그래프의 구성에 등장하는 12각 별 모양이 나우루의 국기에 등장하는 별과 흡사하기 때문에 붙여졌다.