The generalized Kautz digraphs have many good properties as interconnection network topologies. In this note, the bounds of the absorbant number for the generalized Kautz digraph are given, and some sufficient conditi...The generalized Kautz digraphs have many good properties as interconnection network topologies. In this note, the bounds of the absorbant number for the generalized Kautz digraph are given, and some sufficient conditions for the absorbant number of the generalized Kautz digraph attaining the bounds are presented.展开更多
Let G= （V,A） be adigraph and k ≥ 1 an integer. For u,v ∈ V, we say that the vertex u distance k-dominate v if the distance from u to v at most k. A set D of vertices in G is a distance k-dominating set if each ver...Let G= （V,A） be adigraph and k ≥ 1 an integer. For u,v ∈ V, we say that the vertex u distance k-dominate v if the distance from u to v at most k. A set D of vertices in G is a distance k-dominating set if each vertex of V ／ D is distance k-dominated by some vertex of D. The distance k-domination number of G, denoted by γk（G）, is the minimum cardinality of a distance k-dominating set of G. Generalized de Bruijn digraphs GB（n, d） and generalized Kautz digraphs Gg（n, d） are good candidates for interconnection k networks. Denote △k ：=（∑j^k=0 d^j）^-1. F. Tian and J. Xu showed that [n△k] ≤ γk（GB（n,d）） ≤ [n/d^k] and [n△k] ≤ γk（GK（n,d）） ≤ [n/d^k]. In this paper, we prove that every generalized de Bruijn digraph GB（n, d） has the distance k- domination number [n△k] or [n△k] ＋ 1, and the distance k-domination number of every generalized Kautz digraph GK（n, d） bounded above by [n/ （d^k-1 ＋d^k）]. Additionally, we present various sufficient conditions for γk（GB（n, d）） = [n△k] and γk（GK（n, d）） = [n△k].展开更多
The h-super connectivity κh and the h-super edge-connectivity λh are more refined network reliability indices than the conneetivity and the edge-connectivity. This paper shows that for a connected balanced digraph D...The h-super connectivity κh and the h-super edge-connectivity λh are more refined network reliability indices than the conneetivity and the edge-connectivity. This paper shows that for a connected balanced digraph D and its line digraph L, if D is optimally super edge-connected, then κ1（L） = 2λ1 （D）, and that for a connected graph G and its line graph L, if one of κ1 （L） and λ（G） exists, then κ1（L） = λ2（G）. This paper determines that κ1（B（d, n） is equal to 4d- 8 for n = 2 and d ≥ 4, and to 4d-4 for n ≥ 3 and d ≥ 3, and that κ1（K（d, n）） is equal to 4d- 4 for d 〉 2 and n ≥ 2 except K（2, 2）. It then follows that B（d,n） and K（d, n） are both super connected for any d ≥ 2 and n ≥ 1.展开更多
基金supported by the National Natural Science Foundation of China (Grant Nos.10571117,60773078)Shu Guang Plan of Shanghai Education Development Foundation (Grant No.06SG42)the Shanghai Leading Academic Discipline Project(Grant No.J50101)
文摘The generalized Kautz digraphs have many good properties as interconnection network topologies. In this note, the bounds of the absorbant number for the generalized Kautz digraph are given, and some sufficient conditions for the absorbant number of the generalized Kautz digraph attaining the bounds are presented.
基金Acknowledgements This work was supported in part by the National Natural Science Foundation of China （Grant Nos. 11471210, 11571222, 11601262）.
文摘Let G= （V,A） be adigraph and k ≥ 1 an integer. For u,v ∈ V, we say that the vertex u distance k-dominate v if the distance from u to v at most k. A set D of vertices in G is a distance k-dominating set if each vertex of V ／ D is distance k-dominated by some vertex of D. The distance k-domination number of G, denoted by γk（G）, is the minimum cardinality of a distance k-dominating set of G. Generalized de Bruijn digraphs GB（n, d） and generalized Kautz digraphs Gg（n, d） are good candidates for interconnection k networks. Denote △k ：=（∑j^k=0 d^j）^-1. F. Tian and J. Xu showed that [n△k] ≤ γk（GB（n,d）） ≤ [n/d^k] and [n△k] ≤ γk（GK（n,d）） ≤ [n/d^k]. In this paper, we prove that every generalized de Bruijn digraph GB（n, d） has the distance k- domination number [n△k] or [n△k] ＋ 1, and the distance k-domination number of every generalized Kautz digraph GK（n, d） bounded above by [n/ （d^k-1 ＋d^k）]. Additionally, we present various sufficient conditions for γk（GB（n, d）） = [n△k] and γk（GK（n, d）） = [n△k].
基金Supported by the National Natural Science Foundation of China(No.10271114,No.10301031).
文摘The h-super connectivity κh and the h-super edge-connectivity λh are more refined network reliability indices than the conneetivity and the edge-connectivity. This paper shows that for a connected balanced digraph D and its line digraph L, if D is optimally super edge-connected, then κ1（L） = 2λ1 （D）, and that for a connected graph G and its line graph L, if one of κ1 （L） and λ（G） exists, then κ1（L） = λ2（G）. This paper determines that κ1（B（d, n） is equal to 4d- 8 for n = 2 and d ≥ 4, and to 4d-4 for n ≥ 3 and d ≥ 3, and that κ1（K（d, n）） is equal to 4d- 4 for d 〉 2 and n ≥ 2 except K（2, 2）. It then follows that B（d,n） and K（d, n） are both super connected for any d ≥ 2 and n ≥ 1.
