The 3∗3∗-connected property of pyramid networks

A kk-container  C(u,v)C(u,v) of a graph GG is a set of kk-disjoint paths joining uu to vv. A kk-container C(u,v)C(u,v) of GG is a k∗k∗-container   if it contains all the vertices of GG. A graph GG is k∗k∗-connected   if there exists a k∗k∗-container between any two distinct vertices in GG. Let κ(G)κ(G) be the connectivity of GG. A graph GG is superconnected   if GG is i∗i∗-connected for all 1≤i≤κ(G)1≤i≤κ(G). The pyramid network is one of the important networks applied in parallel and distributed computer systems. The connectivity of a pyramid network is three. In this paper, we prove that the pyramid network PM[n]PM[n] is 3∗3∗-connected and superconnected for n≥1n≥1.