Some Properties Of Star Connected Cycles Networks And Triangle Tower Networks

Interconnection network is an important part of super computers. When design and select a topological structure for an interconnection network, hamiltonian and fault tolerance is a significant index for evaluating the performance of network, while the conditional connectivity and the restricted connectivity offer metric parameters to measure the reliability of networks.In this paper, we consider the star connected cycles networks and the triangle tower networks obtain the following results:1.The main results about star connected cycles networks:In 2010, Haizhong Shi proposed a conjecture:for any integer n≥ 4, star connected cycles networks is a union of a edge-disjoint hamiltonian cycles and a perfect matching.we prove the conjecture is true for n=4.In addition the following results are obtained. (1) Star connected cycles networks exist cycles of 3 · 2l(3≤l≤ n!/2), and whe n= 4,4 - SCC is a hamilton graph, while n=5, we found there exists even cycles from 18 to 400 in 5 - SCC.(2) Complete binary trees can embed to the star connected cycles network and its dilation is 1. At the same time, the article provide the constructive methods of the complete binary tree embedding to star connected cycle network. (3) Through analyzing the Star connected cycles networks, we obtain the conditional vertex connectivity and restricted vertex connectivity of Star connected cycles networks. we know when n=3, κ1(3-SCC)=2. when n=4,K1(4-SCC)=3. when n≥5,κ1(n-SCC)=4. and when n≥4 K2(n - SCC)= n - 1. And the 1-conditional vertex connectivity is equal to 2-restricted vertex connectivity of Star connected cycles networks.2.The main results about star connected cycles networks:(1) we analyze a new interconnection network called triangle tower graph. It is maximally connected and tightly super-connected, for n≥ 4, i.e. the connectivity of TTn is 2n - 3. The star graph is subgraph of triangle tower graph, so, the star networks can embed to triangle tower networks and its dilation is 1. (2) we obtain the diameter of triangle tower networks is [3(n-1)-1/2], the average distance is n+2/n-1-2Hn/n(n-1)-Hn.(3) We also propose one variety conjectures on hamiltonicity of triangle tower graph. Conjectures as follow:for any integer n≥ 3, triangle tower networks is a union of κ(1≤ k≤n-2) edge-disjoint hamiltonian cycles and 2n - 3 - 2k perfect matching, and the perfect matching and hamiltonian cycles is edge-disjoint.we also prove conjectures are true for n=3,4 and n=5,6, κ=1,2.