強正則圖的擴大、放大與增大

Abstract

本論文所研究的在於強正則圖的擴大（expander）、放大（magnifier）與增大（enlarger）三者之間的關聯。擴大（expander）是指兩部分點數一樣的二分圖中，符合一部分之中點的子集合不大於一部分點數的一半，點的子集合的鄰居數與其大小的關係。放大（magnifier）是指在圖中，任意子集合符合不大於全部點數的一半，其鄰居數與自身個數的比較。增大（enlarger）是指出圖的第二小的特徵值的特性。藉由強正則圖已經知道所有的特徵值來探討這三者的關係。

The notions of expanders, magnifiers, and enlargers are first in this thesis with focus on their relationship with eigenvalues of some associated matrices including adjacency matrices. They are then further studied among strongly regular graphs by taking advantage of the explicit relations between their parameters and eigenvalues.