The k-Diameter of a Kind of Circulant Graph

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. I…

The k-Diameter of a Kind of Circulant Graph

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.