콕시터 그래프

콕시터 그래프
콕시터 그래프
이름을 따서 명명됨	H. S. M. 콕시터
정점	28
가장자리	42
반지름	4
지름	4
둘레	7
자동형성	336(PGL2(7))
색수	3
색도 지수	3
책두께	3
대기열 번호	2
특성.	대칭 거리-정규어 거리-변환 큐빅 차하밀턴주의
그래프 및 모수 표

그래프 이론의 수학적 분야에서 Coxeter 그래프는 정점 28개와 가장자리 42개를 가진 3-정규 그래프다.^[1]이것은 알려진 13개의 세제곱 거리 정규 그래프 중 하나이다.^[2]그것은 해롤드 스콧 맥도널드 콕시터의 이름을 따서 지어졌다.

특성.

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

콕시터 그래프는 저자극이다. 그 자체로 해밀턴 사이클이 있는 것이 아니라 정점 하나를 제거하여 형성된 모든 그래프는 해밀턴 사이클이다.직선으로 교차하는 숫자 11을 가지며, 교차 번호를^[4] 가진 가장 작은 입방 그래프(OEIS에서 연속 A110507)이다.

건설

Coxeter 그래프의 가장 간단한 구성은 Fano 평면에서 나온 것이다.7개의 물체에 대해₃ C = 35개의 가능한 3-조합을 취한다.28개의 트리플릿을 남기고 파노 평면의 라인에 해당하는 트리플릿 7개를 폐기한다.세 쌍둥이가 분리되어 있으면 두 쌍둥이를 연결하십시오.결과는 Coxeter 그래프 입니다.이 구조는 Kneser 그래프_7,3 KG의 유도 서브그래프로 Coxeter 그래프를 나타낸다.

또한 Coxeter 그래프는 Heawood 그래프에서 각 6 사이클에 대한 꼭지점과 각 6 사이클의 각 쌍에 대한 가장자리를 구성하여 더 작은 거리 정규 Heawood 그래프에서 구성할 수 있다.^[5]

Coxeter 그래프는 Hoffman-Singleton 그래프에서 파생될 수 있다.호프만-싱글턴 그래프에서 정점 v를 취하십시오.v. v. v의 인접 7개를 포함하는 15 크기의 독립 집합이 있으며, 콕시터 그래프를 남겨두고 v를 포함한 전체 독립 집합이 있다.

대수적 특성

Coxeter 그래프의 자동형성 그룹은 순서 336의 그룹이다.^[6]그것은 정점, 가장자리, 그리고 그래프의 호에서 전이적으로 작용한다.따라서 Coxeter 그래프는 대칭 그래프다.그것은 어떤 정점과 어떤 가장자리로도 가져가는 자동모형을 가지고 있다.포스터 인구조사에 따르면 F28A로 참조되는 콕시터 그래프는 28개의 정점에 대한 유일한 입방 대칭 그래프다.^[7]

또한 Coxeter 그래프는 인접 행렬의 그래프 고유값 집합인 그래프 스펙트럼에 의해 고유하게 결정된다.^[8]

해밀턴 사이클이 없는 유한 연결 정점 변환 그래프로서, 콕시터 그래프는 로바스 추측의 변종에 대한 백범례지만, 추측의 규범적 공식은 해밀턴 경로를 요구하고 콕시터 그래프에 의해 검증된다.

해밀턴 주기가 없는 정점 변환 그래프의 예로는 전체 그래프₂ K, 피터슨 그래프, 콕시터 그래프와 각 정점을 삼각형으로 대체하여 피터슨과 콕시터 그래프에서 파생된 두 개의 그래프만 알려져 있다.^[9]

Coxeter 그래프의 특성 ${\displaystyle \mathrm{다항식}}$은${\displaystyle }$( ${\displaystyle \mathrm{x}}$- 3${\displaystyle }$)${\displaystyle }$( ${\displaystyle x}$- ${\displaystyle 2{}^{}}$) ${\displaystyle {8\mathrm{}}^{}}$( x${\displaystyle }$+ ${\displaystyle 1{}^{}}$) ${\displaystyle {7\mathrm{}}^{}}$( ${\displaystyle {}^{}}$ ${\displaystyle {2\mathrm{}}^{}}$+ 2 ${\displaystyle \mathrm{x}}$- ${\displaystyle 1{}^{}}$) 6 ( x 2 + 2 ${\displaystyle x}$ - 1) ${\displaystyle {6\mathrm{}}^{}}$($x-3)(x-2)^{8}(x+1)^{7}(x^{2}+2x-1$)이다$.$$^{6$ 이 특성 다항식을 가진 유일한 그래프로, 스펙트럼에 의해 결정되는 그래프가 된다.

갤러리

• 

  콕시터로부터 어떤 가장자리 절연으로 얻은 그래프는 해밀턴과 연결되어 있다.

• 

  Coxeter 그래프의 색상은 3이다.

• 

  Coxeter 그래프의 직선 교차 번호는 11이다.

참조

• Coxeter, H. S. M. "My Graph." Proc.런던 수학.Soc. 46, 117-136, 1983.