나우루 그래프

나우루 그래프
나우루 그래프는 해밀턴식이다.
정점	24
가장자리	36
반지름	4
지름	4
둘레	6
자동형성	144(S4×S3)
색수	2
색도 지수	3
책두께	3
대기열 번호	2
특성.	대칭 큐빅 해밀턴어 적분 케이리 그래프 양립자
그래프 및 모수 표

그래프 이론의 수학적 분야에서 나우루 그래프는 24개의 정점과 36개의 가장자리를 가진 대칭적인 초당적 입방 그래프다.데이비드 엡스타인이 나우루의 국기에 있는 12점짜리 별의 이름을 따서 지은 것이다.^[1]

색도 번호 2, 색도 지수 3, 지름 4, 반지름 4, 둘레 6을 가지고 있다.^[2]또한 3-Vertex 연결, 3-edge 연결 그래프이기도 하다.책 두께 3과 줄 2가 있다.^[3]

나우루 그래프는 비행기의 어떤 도면에서도 최소한 8개의 교차점을 필요로 한다.이것은 8개의 교차점이 필요한 가장 작은 입방형 그래프와 같은 다섯 개의 비이형 그래프 중 하나이다.이 다섯 개의 그래프 중 또 다른 것은 (3-7)-cage라고도 알려진 McGee 그래프다.^[4][5]

건설

나우루 그래프는 해밀턴식이며 LCF 표기법 [5, -9, 7, -7, 9, -5]^4[1]로 설명할 수 있다.

나우루 그래프는 12점 별의 정점에 연결된 도데각형의 정점에 의해 형성되는 일반화된 피터슨 그래프 G(12, 5)로도 구성될 수 있으며, 별의 각 점이 그것으로부터 5계단 떨어진 지점에 연결된다.

나우루 그래프의 조합형 구조도 있다.구별할 수 있는 물체를 세 개씩 취하여 상자당 하나의 물체를 넘지 않게 구별할 수 있는 4개의 상자에 넣는다.그래프의 24 꼭지점에 해당하는 24가지 방법으로 객체를 분산시킬 수 있다.만약 하나의 물체를 현재의 위치에서 빈 상자로 정확히 이동시킴으로써 한 상태에서 다른 상태로 갈 수 있다면, 두 상태에 해당하는 정점이 에지로 결합된다.그 결과의 상태 변환 그래프는 나우루 그래프다.

대수적 특성

나우루 그래프의 자동형 집단은 순서 144의 집단이다.^[6]대칭군 S와₄ S의₃ 직접적인 산물에 이형성이며, 정점, 가장자리, 그래프의 호에서 전이적으로 작용한다.따라서 나우루 그래프는 대칭 그래프(거리 전이성은 아니지만)이다.그것은 어떤 정점과 어떤 가장자리로도 가져가는 자동모형을 가지고 있다.포스터 인구조사에 따르면, 나우루 그래프는 24개의 정점에 있는 유일한 입방 대칭 그래프다.^[2]

일반화된 피터슨 그래프 G(n,k)는 n = 10과 k =2일 경우 또는 k k² ±1(mod n)인 경우에만 정점 변환이고 (n,k) = (4,k), (5,2), (8,3), (10,3), (10,3), (12,5), (24,5)의 7가지 경우에만 에지 변환이다.^[7]그래서 나우루 그래프는 7개의 대칭적인 일반화된 피터슨 그래프 중 하나이다.Among these seven graphs are the cubical graph ${\displaystyle G(4,1)}$, the Petersen graph ${\displaystyle G(5,2)}$, the Möbius–Kantor graph ${\displaystyle G(8,3)}$, the dodecahedral graph ${\displaystyle G(10,2)}$ and the Desargues graph ${\displaystyle G$$(10,3)}$.

나우루 그래프는 첫 번째 원소를 다른 세 가지 방법 중 하나, 즉 (1 2), (1 3) 및 (1 4)와 스와핑하는 세 가지 다른 방법에 의해 생성된 네 가지 원소의 대칭적 순열 그룹인 S의₄ Cayley 그래프다.

나우루 그래프의 특성 다항식은

${\displaystyle (x-3)(x-2)^{6}(x-1)^{3}x^{4}(x+1)^{3}(x+2)^{6}(x+3)^{6}(x+3)\ }$

스펙트럼 전체가 정수로 구성된 그래프인 적분 그래프.

위상학적 특성

나우루 그래프는 일반화된 일반 다면체로서 두 개의 서로 다른 임베딩이 있다. 즉, 가장자리, 꼭지점 및 면으로 분할된 위상학적 표면이 다른 국기로 어떤 국기(정점, 가장자리, 얼굴의 입사 3중)를 가져가는 대칭이 있는 방식이다.^[8]

이 두 개의 임베딩 중 하나는 토러스(torus)를 형성하기 때문에 나우루 그래프는 토로이드 그래프로서, 12개의 육각형 면과 24개의 정점과 36개의 가장자리로 구성되어 있다.이 임베딩의 이중 그래프는 정점이 12개, 가장자리가 36개인 대칭 6-정규 그래프다.

나우루 그래프의 다른 대칭 임베딩은 6개의 도십각형 면을 가지고 있으며, 속 4의 표면을 형성한다.각각의 면은 다른 면 4개와 가장자리 3개를 공유하기 때문에 이중은 단순한 그래프가 아니다.이 이중은 각 가장자리를 세 개의 평행 가장자리의 묶음으로 교체함으로써 일반 팔면체의 그래프에서 형성될 수 있다.

이 두 개의 임베딩 중 어느 한 개의 얼굴 세트는 다른 임베딩의 페트리 폴리곤 세트다.

기하학적 특성

모든 일반화된 피터슨 그래프와 마찬가지로, 나우루 그래프는 인접한 정점이 단위 거리 거리에 있는 방식으로 평면의 점으로 나타낼 수 있다. 즉, 단위 거리 그래프다.^[9]그것과 프리즘은 도면의 대칭이 n의 주기적 그룹을 형성할 정도로 나타낼 수 없는 유일한 일반화된 피터슨 그래프 G(n,p)이다.대신, 그것의 단위 거리 그래프 표현은 그것의 대칭 그룹으로 이음 그룹 Dih를₆ 가지고 있다.

역사

나우루 그래프에 대해 처음 쓴 사람은 모든 입방체 대칭 그래프를 수집하기 위한 노력의 일환으로 R. M. 포스터였다.^[10]입방체 대칭 그래프의 전체 목록은 현재 포스터 센서스의 이름을 따서 명명되었으며, 이 목록 안에 나우루 그래프는 그래프 F24A로 번호가 매겨져 있지만 구체적인 이름은 없다.^[11]1950년 H. S. M. Coxeter는 이 글을 설명하는 데 사용된 해밀턴식 표현을 두 번째로 인용하여 자카리아스가 발견한 투영형 구성을 Levi 그래프라고 기술했다.^[12][13]

2003년 에드 페그는 자신의 온라인 MAA 칼럼에서 F24A는 이름을 가질 만하지만 이름을 제안하지는 않았다고 썼다.^[14]마침내 2007년에 데이비드 엡스타인은 나우루 공화국의 국기가 일반화된 피터슨 그래프로서 그래프 구성에 나타나는 것과 유사한 12점 별을 가지고 있기 때문에 나우루 그래프라는 이름을 사용했다.^[1]

참조