Spectral radius가 3인 정수의 line graphs의 분류에 관하여

Abstract

연결된 단순 그래프(connected simple graph)$\Gamma$에 대하여, $A$는 $\Gamma$의 인접행렬(adjacency matrix), $D$는 $\Gamma$의 vertex 차수를 대각성분으로 가지는 대각행렬이라 하자. 이 논문에서 우리는 signless Laplace행렬을 $

L

:= D+A$라 정의하고 이 행렬이 오직 정수인 고유치(eigenvalue)를 가지며 스펙트럼 반경(spectral radius, 고유치중 가장 큰 값)이 5인 그래프를 모두 분류하고자 하였다. 이 문제를 해결하기 위하여 우리는 이분 그래프(bipartite graph)와 이분 불가능 그래프(non-bipartite graph)의 경우로 나우어서 그래프를 분류하였다. 그래프 $\Gamma$가 그래프 $H$의 라인 그래프(line graph)일 때, signless Laplace 행렬 $

(H)$가 모두 정수인 고유치(eigenvalue)를 가지며 스펙트럼 반경(spectral radius)을 5로 가지므로, 위의 분류된 결과를 가지고 인접행렬 $A$의 고유치(eigenvalue)가 모두 정수이며 스펙트럼 반경(spectral radius)이 3인 모든 라인 그래프(line graph)를 찾을 수 있었다. 또한 우리는 이러한 성질을 만족하는 그래프를 모두 분류하는 과정에서 그래프의 vertex 개수를 유계화(bounded)하거나 그래프 차수에 관한 여러가지 성질들을 도출하였다.

Let $\Gamma$ be a graph with adjacency matrix $A$ and degree matrix $D$. Thenthe signless Laplace matrix $

$ is defined as $

=D+A$. In this thesis,we classify all graphs $\Gamma$ which signless Laplace matrix has only integraleigenvalues and the spectral radius of $

$ is at most 5. As a consequence wefind all line graphs $\Gamma$ with adjacency integral eigenvalues and spectralradius 3, as, if $\Gamma$ is the line graph of $H$, then $

(H)$ has integraleigenvalues and spectral radius 5.