The Connectivity Of The Network Structure And Completely Positive Matrices

First, we will briefly recall some basic concepts and notation of graph theory used in this article as well as the corresponding backgrounds of networks. Although they have been contained in any standard text-book on graph theory, these concepts defined by one author are different from one by another .In ord er to avoid quibbling it is necessary to present some definitions.Then, because the connectivity, super connectedness, restricted connectivity and restricted-connectivity of a graph are important parameters to measure fault-tolerance of an interconnection network, they are of very important significance in design and analysis of fault-tolerant interconnection network in reality. Some results on this problem will be given in this thesis as follows:1. For Mobius graph, its connectivity and edge-connectivityboth are n , which shows K(MQn) = λ(MQn) = n ,2. Its restricted connectivity and restricted edge-connectivity both are 2n - 2, which shows k'(MQn) =λ(MQn) = 2n - 2.Cycle structure is often used as a connection structure for local area network and as a control and data flow structure for distributed computations in arbitrary networks because of its nice properties such as low connectivity, simplicity, extensibility and its feasible implementation. Therefore, the pancyclicity is a very important measurement for determining whether a topology of network is suitable for an application, where mapping rings of any length into the topology of network is required. By analyzing hypercubes Qn and Mobius and comparing them, then wehave their respective advantages. Although the pancyclic property had been proved, I will still propose the proofs of this property in this article in order to make readers more knowledgeable to the property.A doubly nonnegative matrix A is defined to be an entrywise nonnegative and positive semidifined matrix. It is called completely positive if it can be factored as A =BB', where B is nxm entrywise nonnegative matrix and m is some positive integer. Such number m is called the cprank (oe the factorization index) of A. The present paper gives a survey of the development in this reseach field. Some recent results concerning complete positivity are included.