The k-Diameter of a Kind of Circulant Graph
Zhang Xian-di · Journal of Electronic Science and Technology · 2004
The diameter of a graph G is the maximal distance between pairs of vertices of G. When a network is modeled as a graph,diameter is a measurement for maximum transmission delay. The k-diameter dk(G) of a graph G, which deals with k internally disjoint paths between pairs of vertices of G, is a extension of the diameter of G. It has widely studied in graph theory and computer science. The circulant graph is a group-theoretic model of a class of symmetric interconnection network. Let Cn(i, ) be a circulant graph of order n whose spanning elements are i and , where n≥4 and n is even. In this paper, the diameter, 2-diameter and 3-diameter of the Cn(i, ) are all obtained if gcd(n,i)=1, where the symbol gcd(n,i) denotes the maximum common divisor of n and i. /2 n /2 n /2 n The terminology and notion in this paper are similar to Ref.(1), all graphs discussed here are finite and simple. The diameter d(G) of a graph G is the maximal distance between pairs of vertices of G. The connectivity of G is the minimum number of vertices needed to be removed in order to disconnect the graph. When a network is modeled as a graph,a vertex represents a node of processor (or a station) and an edge between two vertices is the link (or connection) between those two processors. In this context, diameter is a measurement for maximum transmission delay and connectivity is a good parameter to study how much tolerant the network can be in the occasion of node failures. Sometimes, we are interested in looking at a collection of multipaths between a pair of two vertices rather than at a single shortest path between them. So parameters of the k-wide distance (or k-distance) and k-wide diameter (or k-diameter) are introduced. They are extension of distance and diameter. Some kinds of graphs (or networks), such as cycles, complete graphs, hypercubes, buteerfly-derivative networks,k-regular k-connected graphs and so on,their k-diameters have been studied in Refs.(2~4). In this paper we discuss the k-diameters of some circulant graphs. Given a graph G. For x, y∈V(G), x≠y, let Pk(x, y)