Matsushita's Blog

【グラフ理論とネットワーク理論】Extended Complete Graph

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

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)

Ex. 1 f:id:atiek1121:20170530095406p:plain

Number of nodes Number of branched
Gd d+1 (d+1)d
L(Gd) (d+1)d (d+1)d2
L2(Gd) (d+1)d2 (d+1)d3


Complete graph Extended Complete Graph
正則性 Regularity d-Regular d-Regular
Number of nodes V d + 1 (d + 1)dm
Number of branches E (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)