Let G be a k-connected simple graph with order n. The k-diameter, combining connectivity with diameter, of G is the minimum integer d k(G) for which between any two vertices in G there are at least k internally verte...Let G be a k-connected simple graph with order n. The k-diameter, combining connectivity with diameter, of G is the minimum integer d k(G) for which between any two vertices in G there are at least k internally vertex-disjoint paths of length at most d k(G). For a fixed positive integer d, some conditions to insure d k(G)≤d are given in this paper. In particular, if d≥3 and the sum of degrees of any s (s =2 or 3) nonadjacent vertices is at least n+(s-1)k+1-d, then d k(G)≤d. Furthermore, these conditions are sharp and the upper bound d of k-diameter is best possible.展开更多
Parameters k-distance and k-diameter are extension of the distance and the diameter in graph theory. In this paper, the k-distance dk （x,y） between the any vertices x and y is first obtained in a connected circulant...Parameters k-distance and k-diameter are extension of the distance and the diameter in graph theory. In this paper, the k-distance dk （x,y） between the any vertices x and y is first obtained in a connected circulant graph G with order n （n is even） and degree 3 by removing some vertices from the neighbour set of the x. Then, the k-diameters of the connected circulant graphs with order n and degree 3 are given by using the k-diameter dk （x,y）.展开更多
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...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, n / 2) be a circulant graph of order n whose spanning elements are i and n / 2, where n≥4 and n is even. In this paper, the diameter, 2-diameter and 3-diameter of the Cn(i, n / 2) are all obtained if gcd(n,i)=1, where the symbol gcd(n,i) denotes the maximum common divisor of n and i.展开更多
文摘Let G be a k-connected simple graph with order n. The k-diameter, combining connectivity with diameter, of G is the minimum integer d k(G) for which between any two vertices in G there are at least k internally vertex-disjoint paths of length at most d k(G). For a fixed positive integer d, some conditions to insure d k(G)≤d are given in this paper. In particular, if d≥3 and the sum of degrees of any s (s =2 or 3) nonadjacent vertices is at least n+(s-1)k+1-d, then d k(G)≤d. Furthermore, these conditions are sharp and the upper bound d of k-diameter is best possible.
文摘Parameters k-distance and k-diameter are extension of the distance and the diameter in graph theory. In this paper, the k-distance dk （x,y） between the any vertices x and y is first obtained in a connected circulant graph G with order n （n is even） and degree 3 by removing some vertices from the neighbour set of the x. Then, the k-diameters of the connected circulant graphs with order n and degree 3 are given by using the k-diameter dk （x,y）.
文摘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, n / 2) be a circulant graph of order n whose spanning elements are i and n / 2, where n≥4 and n is even. In this paper, the diameter, 2-diameter and 3-diameter of the Cn(i, n / 2) are all obtained if gcd(n,i)=1, where the symbol gcd(n,i) denotes the maximum common divisor of n and i.
