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 a digraph.A set T of vertices of G is a twin dominating set of G if for every vertex v ∈ V ／ T.There exist u,w ∈ T （possibly u = w） such that （u,v）,（v,w） ∈ A.The twin domination number γ...Let G = （V,A） be a digraph.A set T of vertices of G is a twin dominating set of G if for every vertex v ∈ V ／ T.There exist u,w ∈ T （possibly u = w） such that （u,v）,（v,w） ∈ A.The twin domination number γ＊（G） of G is the cardinality of a minimum twin dominating set of G.In this paper we consider the twin domination number in generalized Kautz digraphs GK（n,d）.In these digraphs,we establish bounds on the twin domination number and give a sufficient condition for the twin domination number attaining the lower bound.We give the exact values of the twin domination numbers by constructing minimum twin dominating sets for some special generalized Kautz digraphs.展开更多
Abstract In this paper, the problem of fault tolerant routings in fault tolerant networks is considered. A routing in a network assigns to each ordered pair of nodes a fixed path. All communication among nodes must ...Abstract In this paper, the problem of fault tolerant routings in fault tolerant networks is considered. A routing in a network assigns to each ordered pair of nodes a fixed path. All communication among nodes must go on this routing. When either a node or a link in a fault tolerant network fails, the communication from one node to another using this faulty element must be sent via one or more intermediate nodes along a sequence of paths determined by this routing. An important and practical problem is how to choose a routing in the network such that intermediate nodes to ensure communication are small for any fault set. Let C d be a directed cycle of order d . In this paper. The author first discusses connectivity of Cartesian product digraphs, then proves that the Cartesian product digraph C d 1 ×C d 2 ×...×C d n (d i≥2,1≤i≤n) has a routing such that at most one intermediate node is needed to ensure transmission of messages among all non faulty nodes so long as the number of faults is less than n . This is a generalization of Dolev et al's result for the n dimensional cube.展开更多
基金Supported by National Natural Science Foundation of China （61273108）, the Scientific Research Foundation for the Returned Overseas Chinese Scholars, State Education Ministry, the Fundamental Research Funds for the Central Universities （106112013CD- JZR175501）
基金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.
基金Project supported by the National Natural Science Foundation of China (Grant Nos.10571117, 60773078)the Shuguang Plan of Shanghai Education Development Foundation (Grant No.06SG42)the Shanghai Leading Academic Discipline Project(Grant No.J50101)
文摘Let G = （V,A） be a digraph.A set T of vertices of G is a twin dominating set of G if for every vertex v ∈ V ／ T.There exist u,w ∈ T （possibly u = w） such that （u,v）,（v,w） ∈ A.The twin domination number γ＊（G） of G is the cardinality of a minimum twin dominating set of G.In this paper we consider the twin domination number in generalized Kautz digraphs GK（n,d）.In these digraphs,we establish bounds on the twin domination number and give a sufficient condition for the twin domination number attaining the lower bound.We give the exact values of the twin domination numbers by constructing minimum twin dominating sets for some special generalized Kautz digraphs.
文摘Abstract In this paper, the problem of fault tolerant routings in fault tolerant networks is considered. A routing in a network assigns to each ordered pair of nodes a fixed path. All communication among nodes must go on this routing. When either a node or a link in a fault tolerant network fails, the communication from one node to another using this faulty element must be sent via one or more intermediate nodes along a sequence of paths determined by this routing. An important and practical problem is how to choose a routing in the network such that intermediate nodes to ensure communication are small for any fault set. Let C d be a directed cycle of order d . In this paper. The author first discusses connectivity of Cartesian product digraphs, then proves that the Cartesian product digraph C d 1 ×C d 2 ×...×C d n (d i≥2,1≤i≤n) has a routing such that at most one intermediate node is needed to ensure transmission of messages among all non faulty nodes so long as the number of faults is less than n . This is a generalization of Dolev et al's result for the n dimensional cube.
