Research On Connectivity Of Some Networks

The connection mode between processors in a massively parallel processor system is called the interconnection network of the system,and the interconnection network can be regarded as a connected graph,the vertices of the graph represent the processors in the system,and the edges of the graph represent the communication links between the processors.Therefore,topological performance of the interconnection network can be measured by the properties and parameters of the graph.Many new and significant concepts of connectivity,such as Super vertex(edge)-connected and restricted(edge-)connectivity,are proposed in the optimal design of interconnection networks.In this paper,we research some connectivity of varietal hypercubes,generalized Johnson graphs and balanced complete multipartite graphs.In first chapter,we introduce the research background and the terminology symbols,and review the research and current situation of various kinds of connectivity,and summarize the main contents and research methods of this paper.In second chapter,we apply the symmetry of the varietal hypercube and the generalized Johnson graph,the Super vertex(edge)-connected,restricted edge-connectivity,super restricted edge-connected,cyclic edge-connectivity and super cyclically edge-connected of these two kinds of graphs are determined.In third chapter,we determine the extra edge-connectivity and component edge-connectivity of balanced complete multipartite graphs by the maximum number of edges of m induced subgraphs.