메러디스 그래프

메러디스 그래프
메러디스 그래프
이름을 따서 명명됨	G. H. 메러디스
정점	70
가장자리	140
반지름	7
지름	8
둘레	4
자동형성	38698352640
색수	3
색도 지수	5
책두께	3
대기열 번호	2
특성.	오일러어
그래프 및 모수 표

그래프 이론의 수학적 분야에서 메러디스 그래프는 1973년 가이 H. J. 메러디스가 발견한 정점 70개와 140개의 가장자리를 가진 4-정기 비방향 그래프다.^[1]

메러디스 그래프는 4-Vertex 연결되고 4-edge 연결되며 색도 번호 3, 색도 지수 5, 반지름 7, 지름 8, 둘레 4이며 해밀턴이 아니다.^[2]책 두께 3과 줄 2가 있다.^[3]

1973년에 출판된 이 책은 크리스핀 내시 윌리아스의 추측에 모든 4개의 정규 4버텍스 연결 그래프가 해밀턴식 그래프라는 것을 반증한다.^[4][5]그러나 W. T. Tutte는 4개의 연결된 평면 그래프가 모두 해밀턴 그래프라는 것을 보여주었다.^[6]

The characteristic polynomial of the Meredith graph is ${\displaystyle (x-4)(x-1)^{10}x^{21}(x+1)^{11}(x+3)(x^{2}-13)(x^{6}-26x^{4}+3x^{3}+169x^{2}-39x-45)^{4}}$.

갤러리

• 

  메러디스 그래프의 색상은 3이다.

• 

  메러디스 그래프의 색지수는 5이다.

참조