Cayley graph is a mathematical model in which all vertices and edges are represented as elements of a finite group G and relations between the elements with respect to some generating set S of G. Since the model is based on rich background of group theory, it has many advantages: the symmetric structures in any Cayley graph make itself preferable as a static interconnection network. Furthermore, sensible choice of its basis group and corresponding generating set can add more desirable properties. So it is widely used in designing and analyzing interconnection networks.
This thesis proposes a new class of Cayley graph based on the linear group PSL(2,p) for a prime power integer p, and considers some of its properties. The graph has $O(p^3)$ nodes and fixed degree 3. Similar to the structure of cube-connected cycle, it consists of interconnected cycles. We show some additional properties of the graph. It is planar for p=3,5 and has maximum connectivity. The hamiltonicity of the graph is also considered. Finally, a simple routing algorithm on the graph is developed, which bounds the diameter of the graph to $O(\sqrt[3]{\mid{V}\mid})$. By experimental results, we conjecture that the diameter of the graph is $O(log\mid{V}\mid)$ in optimum.
케일리 그래프는 유한 그룹으로부터 그래프를 생성해내는 수학적인 모델이다. 여기서 그래프의 정점들과 에지들은 주어진 유한 그룹의 원소들과 그 그룹의 generating set에 대한 원소들의 관계로 나타내어진다. 케일리 그래프는 여러 가지 장점을 가지고 있는데, 그 중 가장 주목할 만한 것은 대칭성을 가지고 있다는 것이다. 이러한 대칭적인 그래프는 바로 상호 연결망으로 응용될 수 있다. 이 대칭성은 많은 장점을 가져오기도 하지만, 실제 그래프의 많은 성질은 그 그래프가 어떤 그룹으로부터 생성되었느냐와 어떤 generating set이 사용되었느냐에 많은 영향을 받는다.
본 논문에서는 선형 그룹 PSL(2,p)로부터 생성되는 케일리 그래프의 성질을 다룬다. 선형 그룹은 최근 분지수와 지름이 작으면서 정점 수가 많은 케일리 그래프를 생성한다고 알려진바 있다. 여기서 제안되는 그래프는 분지수가 3으로 고정되어 있고, 상호 연결된 싸이클들로 이루어졌다는 점에서 cube-connected cycle과 비슷하다. 이 그래프의 보다 다양한 성질들은 선형 그룹의 행렬 표현으로부터 밝혀낼 수 있다. 여기서 제안한 그래프는 p=3,5인 경우 평면상에 그릴 수 있으며, 최대 연결도를 갖는다. 또한, 제안된 그래프가 해밀튼 싸이클을 갖는지의 여부도 알아본다.
