Circulant graphs and their application to communication networks = Circulant 그래프 및 그의 통신망에 대한 응용

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$, $0 \le i \le [log_{d}N]-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
Advisors
Chwa, Kyung-Yongresearcher좌경룡researcher
Publisher
한국과학기술원
Issue Date
1992
Identifier
59808/325007 / 000855156
Language
eng
Description

학위논문(박사) - 한국과학기술원 : 전산학과, 1992.2, [ ix, 104 p. ]

URI
http://hdl.handle.net/10203/32926
Link
http://library.kaist.ac.kr/search/detail/view.do?bibCtrlNo=59808&flag=t
Appears in Collection
CS-Theses_Ph.D.(박사논문)
Files in This Item
There are no files associated with this item.
  • Hit : 267
  • Download : 0
  • Cited 0 times in thomson ci

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0