Introduction
Definitions of chordal ring, average distance and connectivity ratio
Circulant graph and chordal ring
-
Definition 1: G(V, E) is a simple graph with m vertices and n edges. There are integers w 1, w 2, …, w j (w 1 < w 2 < … < w j < (m + 1)/2) that represent a jump sequence. Two vertices v k and v l of V are connected if and only if (k + w i ) mod m = l, or (k – w i ) mod m = l. This graph is defined as a circulant graph. A circulant graph with j jumps is usually denoted by CG(m; w 1, w 2, …, w j ) or CG(m; W) with jump sequence W = {w 1, w 2, …, w j }, and |W| = j.
-
This definition does not guarantee that a circulant graph is connected. For example, CG(8; 1, 2) is a connected circulant graph, but CG(8; 2, 4) is not connected. Boesch and Tindell [5] found that a circulant graph is connected if and only if the greatest common divisor gcd(m, w 1, w 2, …,w j ) is equal to 1. Such a graph is always known as a connected circulant graph. Furthermore, it has been proved that every connected circulant graph has a Hamiltonian cycle [17]. In particular, a complete graph can always be considered as a combination of all CG(m; w i ) (1 ≤ i ≤ ⌊m/2⌋), which are considered as basic parts, as shown in Fig. 1.×
-
In addition, the chordal ring network is introduced. There are two definitions for a chordal ring [13].
-
Definition 2: If a circulant graph CG(m, W) has w 1 equal to 1, it is known as a chordal ring. The edges with w i ≠ w 1 (2 ≤ i ≤ j) are denoted by chords of length w i .
-
Definition 3: G(V, E) is a simple graph with m vertices and n edges. Vertices v 1, v 2, …,v m in V are connected in sequence into a Hamiltonian cycle. There are integers w 1, w 2, …, w j (w 1 < w 2 < … < w j < (m + 1)/2). Two vertices v k and v l of V are connected if and only if k and l are odd numbers, and (k + w i ) mod m = l. This graph is defined as a chordal ring. A circulant graph with j chords is usually denoted by CR(m, w 1, w 2, …, w j ) or CR(m, W).
-
In this work, we consider the former definition of a chordal ring, i.e., Definition 2. From this definition, it can be deduced that a chordal ring is a special case of a connected circulant graph.
Average distance
Connectivity ratio
The Combination Method for topology design
Average distance of chordal ring
-
Proposition 1: G(V, E) is a Hamiltonian cycle, |V| = m (m ≥ 3), |E| = n (n = m). If m is odd, its average distance is (m + 1)/4; if m is even, its average distance is (1/4)[1/(m − 1) + m + 1].
The Combination Method
(a) Type-I | |||||||
k
2
| Col. | 2 | 3 | 4 | |||
k
3
| |||||||
2 | (w
2,w
3) | — | — | — | — | — | — |
D
sel
| — | — | — | — | — | — | |
(w
2,w
3) | — | (48,55) | (40,55) | (32,55) | (30,55) | (24,55) | |
D
sel
| — | 3.3871 | 3.7419 | 3.4516 | 3.5161 | 3.6129 | |
3 | (w
2,w
3) | — | (39,45) | (33,45) | (26,45) | (25,45) | (19,45) |
D
sel
| — | 4.0645 | 3.6613 | 3.6452 | 3.5161 | 3.3871 | |
(w
2,w
3) | — | (31,36) | (27,36) | (20,36) | (20,36) | (15,36) | |
D
sel
| — | 3.5323 | 3.8226 | 3.6613 | 3.6613 | 3.5806 | |
4 | (w
2,w
3) | — | (29,34) | (26,34) | (19,34) | (19,34) | (14,34) |
D
sel
| — | 3.8871 | 3.3387 | 3.7581 | 3.7581 | 3.3871 | |
(w
2,w
3) | — | (22,27) | (21,27) | (15,27) | (15,27) | (11,27) | |
D
sel
| — | 3.6290 | 3.4194 | 3.8871 | 3.8871 | 3.4355 | |
(b) Type-II | |||||||
k
2
| Col. | 2 | 3 | 4 | |||
k
3
| |||||||
2 | (w
2,w
3) | — | (51,52) | (41,52) | (36,52) | (31,52) | (28,52) |
D
sel
| — | 4.5645 | 3.9677 | 4.1774 | 4.1290 | 3.5161 | |
(w
2,w
3) | — | (41,46) | (33,46) | (29,46) | (26,46) | (22,46) | |
D
sel
| — | 3.9516 | 3.9839 | 3.4194 | 3.6452 | 3.8710 | |
3 | (w
2,w
3) | — | (33,37) | (27,37) | (23,37) | (21,37) | (18,37) |
D
sel
| — | 3.4677 | 3.4194 | 3.4194 | 3.4032 | 4.5161 | |
(w
2,w
3) | (30,33) | (26,33) | (22,33) | (18,33) | (17,33) | (14,33) | |
D
sel
| 5.1290 | 3.6935 | 3.5968 | 3.5484 | 4.0323 | 3.4032 | |
4 | (w
2,w
3) | — | (25,29) | (20,29) | (17,29) | (16,29) | (13,29) |
D
sel
| — | 3.5645 | 3.6129 | 3.3710 | 3.5484 | 3.7419 | |
(w
2,w
3) | (23,25) | (19,25) | (16,25) | (14,25) | (13,25) | (10,25) | |
D
sel
| 4.5968 | 3.5323 | 3.5484 | 3.7097 | 4.5968 | 3.4677 |
The Local Search Method for further optimization
Step 1: Calculate the set of jump sequence points surrounding W, which can be denoted by W’ = {w
1', w
2', …,w
j
'}, with w
i
' ∈ (w
i
− α, w
i
+ α). Calculate \( {\overline{D}}_{center}=f\left(m,W\right) \)
Step 2: Calculate all \( {\overline{D}}_{neigh}=f\left(m,W\hbox{'}\;\right) \), and determine the W’
neigh_min
that corresponds to the minimum \( {\overline{D}}_{neigh} \) within the neighborhood. The minimum \( {\overline{D}}_{neigh} \) is denoted by \( {\overline{D}}_{neigh\_ \min } \). Step 3: If \( {\overline{D}}_{neigh\_ \min }<{\overline{D}}_{center} \), set W = W’
neigh_min
, \( {\overline{D}}_{center}={\overline{D}}_{neigh\_ \min } \), and goto Step 1. Otherwise, output W’
neigh_min
. |