평면 및 외평면 그래프의 최대 확산에 대하여

그래프 G의 확산은 G의 인접 행렬의 가장 큰 고윳값과 가장 작은 고윳값의 차이이다. Gotshall, O'Brien, 그리고 Tait는 충분히 큰 n에 대해 최대 확산을 갖는 n-정점 외평면 그래프가 n-1 정점의 경로에 정점을 연결하여 얻은 그래프라고 추측하였다. 본 논문에서는 극단 그래프가 (2n-1)/3 정점의 경로와 (n-2)/3의 고립 정점을 연결하여 얻은 그래프임을 보여줌으로써 이 추측을 반증한다. 평면 그래프의 경우, 최대 확산을 달성하는 극단 n-정점 평면 그래프는 두 개의 인접하지 않은 정점을 (2n-2)/3 정점의 경로와 (n-4)/3의 고립 정점에 연결하여 얻은 그래프임을 보여준다.