In this thesis, network metrics of circulant graphs are investigated, and a new topology of communication networks is proposed. We consider diameters of circulant graphs with degree four of less and diameters of circulant graphs which are isomorphic to the product of two nontrivial circulant graphs. We present a necessary and sufficient condition for a strongly connected circulant digraph with two jumps to have a directed hamiltonian cycle. The problems of constructing circulant minimal broadcast digraphs and regular minimal broadcast digraphs with as small degree as possible are considered.
We propose a construction of circulant graphs with the property that every circulant graph can be obtained by applying the constructions repeatedly to trivial graphs, and give a generalization of the construction by relaxing some constraints posed on the construction. Many graphs including hypercubes with the maximum connectivity and edge connectivity can be obtained by applying the generalized constructions repeatedly to trivial graphs. The connectivity and edge connectivity of graphs obtained by applying the generalized construction to d connected graphs are considered. We also consider the connectivity and edge connectivity of digraphs obtained by applying the digraph-form generalized construction to d strongly connected digraphs.
A new topology of communication networks is proposed. The network G (N, d), d≥2, is a circulant graph with N nodes and jumps $d^i$, 0i$\iceil\log_dN\iceil$-1. The network is vertex transitive (not edge transitive), and has a hamiltonian cycle. The connectivity and edge connectivity, diameter, mean intemode distance, and node visit ratio and edge visit ratio (under the uniform message distribution) of G($cd^m$, d), 1≤c
Circulant그래프의 지름, 해밀톤 특성, 방송, 노드 및 에지 연결도 등 통신망 척도에 대해 고찰하고, Circulant 그래프 부류에 속하는 새로운 통신망의 위상을 제안하였다.
분지수가 4 이하인 Circulant 그래프와 두 Circulant 그래프의 곱으로 표현될 수 있는 Circulant그래프의 지름을 고려하였고, 두 개의 점프를 가진 유향 Circulant그래프가 해밀톤 사이클을 가질 필요 충분 조건을 제시하였다. 그리고 Circulant 그래프와 정규 그래프의 부류에 속하면서 분지수가 작은 최소 시간 방송 유향 그래프를 설계하는 문제를 고려하였다.
모든 Circulant그래프를 하나의 노드만 가진 그래프로부터 반복 적용하여 얻을 수 있는 "설계"를 제시하고, 설계에 가해진 제약을 완화하여 "일반적 설계"를 제시하였다. 일반적 설계를 이용하면 Circulant그래프뿐만 아니라 하이퍼큐브 등 망특성이 좋은 많은 그래프를 얻을 수 있다. 일반적 설계를 이용하여 얻을 수 있는 그래프의 노드 연결도와 에지 연결도를 고찰하였다. 그리고 유향 그래프 형태의 설계와 일반적 설계를 제시하고, 유향 그래프 형태의 일반적 설계를 적용하여 얻을 수 있는 유향 그래프의 노드 및 에지 연결도도 고찰하였다.
새로운 통신망의 위상 G(N, d)를 제안하고, N = $cd^m$(1≤c
