A structure theory for graphs with fixed smallest eigenvalue

Abstract

In 1977, Hoffman gave a characterization of graphs with smallest eigenvalue greater than $-1-\sqrt2$. In this thesis, We utilize the concept of Hoffman graphs, introduced by Woo and Neumaier, to generalize this result for smaller smallest eigenvalue.

Chapter 1 is an introduction of our main topic. Firstly, we give the characterizations of generalized line graphs by Cameron et al. and Hoffman. Secondly, we present the statement of our main results, which are generalizations of a result of Hoffman, and an overview of the known results on Hoffman graphs. In Chapter 2, we introduce some preliminary notions of spectral graph theory and basic definitions of Hoffman graphs, which will be used throughout this thesis.

Chapter 3 and 4 are concerned with the structure theory for graphs with fixed smallest eigenvalue, which is a prerequisite for the proof of the main results. In Chapter 3, we introduce two new concepts, quasi-cliques and associated Hoffman graphs. These two concepts provide the relation between smallest eigenvalue of ordinary graphs and smallest eigenvalue of Hoffman graphs. In Chapter 4, we find some properties of graphs with fixed smallest eigenvalue. These properties are obtained from looking at smallest eigenvalue of associated Hoffman graphs.

Chapter 5 and 6 deal with our main results and their applications. In Chapter 5, we classify all $t$-fat Hoffman graphs with smallest eigenvalue at least $-t-1$. They are characterized by finite number of Hoffman graphs. These Hoffman graphs play key role in the statement of our main results. In Chapter 6, we state our main results, which generalize the characterization of Hoffman. Our main results provide new tools to study the structure of graphs cospectral with the Hamming graph $H(3,q)$, the Johnson graph $J(n,3)$ and the $2$-clique extension of grids.

호프만은 1977년에 최소고유치가 $-1-\sqrt2$보다 크고 최소차수가 충분히 큰 그래프들은 generalized line graph라는 사실을 보였다. 이 논문에서 우리는 이 결과를 일반화하기 위해서 호프만 그래프의 개념을 이용하였다.

1장은 논문의 서론이다. 우리는 호프만의 원 정리와 그와 비교되는 카메론 외 3명의 정리를 제시하고, 그것을 일반화한 우리의 주요 결과를 서술하였다. 2장에서 우리는 이 논문에서 쓰일 그래프 이론과 호프만 그래프에 대한 기본적인 용어와 정리를 소개한다.

3장과 4장은 주요 결과를 보이기 위한 준비 작업인 고정된 최소고유치를 가지는 그래프의 구조 이론에 대한 장들이다. 3장에서는 quasi-clique과 associated 호프만 그래프라는 새로운 두 개념을 소개한다. 이 두 개념은 호프만 그래프와 일반적인 그래프의 최소고유치 사이의 관계를 보여준다. 4장에서는 이 두 개념을 이용해서 고정된 최소고유치를 가지는 그래프가 어떤 성질을 가지는가를 보여준다. 이 성질들은 associated 호프만 그래프의 최소고유치를 관찰함으로써 얻어진다.

5장과 6장은 우리의 주요 결과와 그 응용을 다룬다. 5장에서 우리는 $t$-fat 호프만 그래프 중 최소고유치가 $-t-1$인 모든 호프만 그래프를 분류한다. 이 호프만 그래프들은 유한한 호프만 그래프의 집합인 $\Go(t)$로 표현되고, 이 집합 $\Go(t)$는 우리의 주요 결과를 서술하는데 결정적인 역할을 한다. 6장에서는 호프만의 결과를 일반화하는, 이 논문의 주요 결과 두 개를 서술한다. 이 결과는 해밍 그래프 $H(3,q)$, 존슨 그래프 $J(n,3)$, 그리고 격자 그래프의 $2$-clique extension와 같은 고유치를 가지는 그래프들의 구조를 밝히는데 적용된다.