The Study Of Forwarding Indices And Wide Diameters Of Circulant Graphs

The topological structure of an interconnection network can be usually modeled by a connected graph. The connectivity, forwarding index, diameter and wide diameter of a graph are important parameters for measuring reliability and e?ciency of an interconnection network.Circulant graphs have been extensively investigated over the past 30 years because of their broad application to di?erent ?elds of theory and practice. Thus,the study of the above parameters of the circulant graph and its subgraph-the Toeplitz graph is very important.In this paper, we give the following results.In chapter 2, on the study of the forwarding index of the circulant graph, we construct shortest paths whose expressions are speci?cally given between any two distinct vertices and obtain the exact values of vertex-forwarding indices of 4-regular circulant graphs with order n(n ≥ 6). Furthermore, based on the relations, known so far, between vertexforwarding indices and edge forwarding indices, some bounds of edge forwarding indices for this kind of graphs can be presented immediately.In chapter 3, about the study of the wide diameters of the circulant graph with degree 4, we give a family of four internally disjoint paths between any two vertices of the circulant graph with degree 4 by construction. Moreover, one upper bound of 4-wide diameter of the kind of the circulant graph is also given.In chapter 4, for the Toeplitz graph, we prove that the connectivity of Tn(1, d), as a subgraph of the circulant graph, is 2 and give the concrete expressions of a family of two internally disjoint paths between any two vertices of it by construction. Moreover,the exact values of the diameters and some sharp upper bounds of wide diameters of the Toeplitz graph Tn(1, d) are also presented.