Connectivity and Damage Index
Connectivity express the reliability of the graph
- Node Connectivity Cv(G) : Minimum number of nodes to be removed to make a graph unconnected.
- Branch Connectivity Ce(G) : Minimum number of branches to be removed to make a graph unconnected.
- Node connectivity = d → d - 1 node failures OK
- Branch connectivity = d → d - 1 branch failures OK
Cv(G) ≦ Ce(G) ≦ δ(G) : δ = degree (the number of branches of one node)
Damage index is an index of the increase of hops to connect in case of failure.
α-Node(Branch) Damage Index Iα(G) (Jα(G)) is defined as blow
Maximum diameter of a graph without α nodes(branches)-
Diameter of the original graph G
Design Method of Extended Complete Graph
Extended Complete Graph : Complete graph Gd → Line conversion, m times → Extended complete graph.
Lm(Gd) = L(L(…(L(G))…)) (m times)
|Number of nodes||Number of branched|
|Complete graph||Extended Complete Graph|
|Number of nodes
||d + 1||(d + 1)dm|
|Number of branches
||(d + 1)d||(d+1)dm+1|
|直径 Diameter k(G)||1||m+1|
|Node connectivity Cv(G)||d||d|
|Branch connectivity Ce(G)||d||d|
|次数 Degree δ(G)||d||d|
|節点罹障度 Node damage index Iα(G)||0||≦ m|
|枝罹障度 Branch damage index Jα(G)||1||≦ m+1|
Throughput ratio in case of failure
k(G)/(Jα(G) + k(G)) → 0.5 for both Gd and Lm(Gd)