The （conditional） matching preclusion number of a graph is the minimum number of edges whose deletion leaves a resulting graph （with no isolated vertices） that has neither perfect matchings nor almost perfect matc...The （conditional） matching preclusion number of a graph is the minimum number of edges whose deletion leaves a resulting graph （with no isolated vertices） that has neither perfect matchings nor almost perfect matchings. In this paper, we find this number and classify all optimal sets for the augmented k-ary n-cubes with even k ≥ 4.展开更多
The 3-ary n-cube,denoted as Qn3,is an important interconnection network topology proposed for parallel computers,owing to its many desirable properties such as regular and symmetrical structure,and strong scalability,...The 3-ary n-cube,denoted as Qn3,is an important interconnection network topology proposed for parallel computers,owing to its many desirable properties such as regular and symmetrical structure,and strong scalability,among others.In this paper,we first obtain an exact formula for the minimum wirelength to embed Qn3 into grids.We then propose a load balancing algorithm for embedding Qn3 into a square grid with minimum dilation and congestion.Finally,we derive an O(N2)algorithm for embedding Qn3 into a gird with balanced communication,where N is the number of nodes in Qn3.Simulation experiments are performed to verify the total wirelength and evaluate the network cost of our proposed embedding algorithm.展开更多
The shortest k-dimension paths (k-paths) between vertices of n-cube are considered on the basis a bijective mapping of k-faces into words over a finite alphabet. The presentation of such paths is proposed as (n - k + ...The shortest k-dimension paths (k-paths) between vertices of n-cube are considered on the basis a bijective mapping of k-faces into words over a finite alphabet. The presentation of such paths is proposed as (n - k + 1)×n matrix of characters from the same alphabet. A classification of the paths is founded on numerical invariant as special partition. The partition consists of n parts, which correspond to columns of the matrix.展开更多
The k-ary n-cube Qkn （n ≥2 and k ≥3） is one of the most popular interconnection networks. In this paper, we consider the problem of a fault- free Hamiltonian cycle passing through a prescribed linear forest （i.e....The k-ary n-cube Qkn （n ≥2 and k ≥3） is one of the most popular interconnection networks. In this paper, we consider the problem of a fault- free Hamiltonian cycle passing through a prescribed linear forest （i.e., pairwise vertex-disjoint paths） in the 3-ary n-cube Qn^3 with faulty edges. The following result is obtained. Let E0 （≠θ） be a linear forest and F （≠θ） be a set of faulty edges in Q3 such that E0∩ F = 0 and ｜E0｜ ＋｜F｜ ≤ 2n - 2. Then all edges of E0 lie on a Hamiltonian cycle in Qn^3- F, and the upper bound 2n - 2 is sharp.展开更多
The resistance seen into the port in an n-cube formed by two vertices of distance n-1 is exactly formulated for any positive integer n. The resistances seen into the port in an n-cube formed by any two vertices is al...The resistance seen into the port in an n-cube formed by two vertices of distance n-1 is exactly formulated for any positive integer n. The resistances seen into the port in an n-cube formed by any two vertices is also found by experiments for 1 n7.展开更多
in this paper, we present a new unidirectional graph, the 'alternating graph. Like the known (unidirectional) n-cube and (unidirectional) n-star, the alternating graph is shown to possess rich structure and symmet...in this paper, we present a new unidirectional graph, the 'alternating graph. Like the known (unidirectional) n-cube and (unidirectional) n-star, the alternating graph is shown to possess rich structure and symmetry properties as well as many desirable fault tolerant characteristics展开更多
文摘The （conditional） matching preclusion number of a graph is the minimum number of edges whose deletion leaves a resulting graph （with no isolated vertices） that has neither perfect matchings nor almost perfect matchings. In this paper, we find this number and classify all optimal sets for the augmented k-ary n-cubes with even k ≥ 4.
基金the National Key Research and Development Program of China under Grant No.2018YFB1003201the National Natural Science Foundation of China under Grant Nos.61572337,61602261,61672296,and 61872257+4 种基金Jiangsu High Technology Research Key Laboratory for Wireless Sensor Networks Foundation under Grant No.WSNLBKF201701the Scientific & Technological Support Project of Jiangsu Province of China under Grant Nos.BE2016777,BE2016185,and BE2017166China Postdoctoral Science Foundation under Grant No.172985the Natural Science Foundation of the Jiangsu Higher Education Institutions of China under Grant No.17KJB520036Jiangsu Planned Projects for Postdoctoral Research Funds under Grant No.1701172B.
文摘The 3-ary n-cube,denoted as Qn3,is an important interconnection network topology proposed for parallel computers,owing to its many desirable properties such as regular and symmetrical structure,and strong scalability,among others.In this paper,we first obtain an exact formula for the minimum wirelength to embed Qn3 into grids.We then propose a load balancing algorithm for embedding Qn3 into a square grid with minimum dilation and congestion.Finally,we derive an O(N2)algorithm for embedding Qn3 into a gird with balanced communication,where N is the number of nodes in Qn3.Simulation experiments are performed to verify the total wirelength and evaluate the network cost of our proposed embedding algorithm.
文摘The shortest k-dimension paths (k-paths) between vertices of n-cube are considered on the basis a bijective mapping of k-faces into words over a finite alphabet. The presentation of such paths is proposed as (n - k + 1)×n matrix of characters from the same alphabet. A classification of the paths is founded on numerical invariant as special partition. The partition consists of n parts, which correspond to columns of the matrix.
基金Acknowledgements The author would like to thank the anonymous referees for their valuable suggestions. This work was supported by the Natural Science Foundation of Fujian Province （No. 2011J01025）.
文摘The k-ary n-cube Qkn （n ≥2 and k ≥3） is one of the most popular interconnection networks. In this paper, we consider the problem of a fault- free Hamiltonian cycle passing through a prescribed linear forest （i.e., pairwise vertex-disjoint paths） in the 3-ary n-cube Qn^3 with faulty edges. The following result is obtained. Let E0 （≠θ） be a linear forest and F （≠θ） be a set of faulty edges in Q3 such that E0∩ F = 0 and ｜E0｜ ＋｜F｜ ≤ 2n - 2. Then all edges of E0 lie on a Hamiltonian cycle in Qn^3- F, and the upper bound 2n - 2 is sharp.
文摘The resistance seen into the port in an n-cube formed by two vertices of distance n-1 is exactly formulated for any positive integer n. The resistances seen into the port in an n-cube formed by any two vertices is also found by experiments for 1 n7.
基金Trans-Century Training Programme Foundation for the Talents by the StateEducation Commission.
文摘in this paper, we present a new unidirectional graph, the 'alternating graph. Like the known (unidirectional) n-cube and (unidirectional) n-star, the alternating graph is shown to possess rich structure and symmetry properties as well as many desirable fault tolerant characteristics
