Let Qn,k （n 〉 3, 1 〈 k ≤ n - 1） be an n-dimensional enhanced hypercube which is an attractive variant of the hypercube and can be obtained by adding some complementary edges, fv and fe be the numbers of faulty ve...Let Qn,k （n 〉 3, 1 〈 k ≤ n - 1） be an n-dimensional enhanced hypercube which is an attractive variant of the hypercube and can be obtained by adding some complementary edges, fv and fe be the numbers of faulty vertices and faulty edges, respectively. In this paper, we give three main results. First, a fault-free path P[u, v] of length at least 2n - 2fv - 1 （respectively, 2n - 2fv - 2） can be embedded on Qn,k with fv ＋ f≤ n- 1 when dQn,k （u, v） is odd （respectively, dQ,~,k （u, v） is even）. Secondly, an Q,,k is （n - 2） edgefault-free hyper Hamiltonianaceable when n （ 3） and k have the same parity. Lastly, a fault-free cycle of length at least 2n - 2fv can be embedded on Qn,k with f~ 〈 n - 1 and fv＋f≤2n-4.展开更多
The （s＋t＋1）-dimensional exchanged crossed cube, denoted as ECQ（s, t）, combines the strong points of the exchanged hypercube and the crossed cube. It has been proven that ECQ（s, t） has more attractive propertie...The （s＋t＋1）-dimensional exchanged crossed cube, denoted as ECQ（s, t）, combines the strong points of the exchanged hypercube and the crossed cube. It has been proven that ECQ（s, t） has more attractive properties than other variations of the fundamental hypercube in terms of fewer edges, lower cost factor and smaller diameter. In this paper, we study the embedding of paths of distinct lengths between any two different vertices in ECQ（s, t）. We prove the result in ECQ（s, t）： if s≥3, t≥3, for any two different vertices, all paths whose lengths are between max{9,「s＋1/2」 ＋「t＋1/2＋4}and 2s＋t＋1？1 can be embedded between the two vertices with dilation 1. Note that the diameter of ECQ（s, t） is「s＋1/2 」＋「t＋1/2 」＋2. The obtained result is optimal in the sense that the dilations of path embeddings are all 1. The result reveals the fact that ECQ（s, t） preserves the path embedding capability to a large extent, while it only has about one half edges of CQn.展开更多
基金supported by NSFC (11071096, 11171129)NSF of Hubei Province, China (T201103)
文摘Let Qn,k （n 〉 3, 1 〈 k ≤ n - 1） be an n-dimensional enhanced hypercube which is an attractive variant of the hypercube and can be obtained by adding some complementary edges, fv and fe be the numbers of faulty vertices and faulty edges, respectively. In this paper, we give three main results. First, a fault-free path P[u, v] of length at least 2n - 2fv - 1 （respectively, 2n - 2fv - 2） can be embedded on Qn,k with fv ＋ f≤ n- 1 when dQn,k （u, v） is odd （respectively, dQ,~,k （u, v） is even）. Secondly, an Q,,k is （n - 2） edgefault-free hyper Hamiltonianaceable when n （ 3） and k have the same parity. Lastly, a fault-free cycle of length at least 2n - 2fv can be embedded on Qn,k with f~ 〈 n - 1 and fv＋f≤2n-4.
基金This work is supported by the National Natural Science Foundation of China under Grant Nos. 61572337 and 61502328, the Program for Postgraduates Research Innovation in University of Jiangsu Province under Grant No. KYLX16_0126, Collaborative Innovation Center of Novel Software Technology and Industrialization, and tile Natural Science Foundation of tile Jiangsu Higher Education Institutions of China under Grant No. 14KJB520034.
文摘The （s＋t＋1）-dimensional exchanged crossed cube, denoted as ECQ（s, t）, combines the strong points of the exchanged hypercube and the crossed cube. It has been proven that ECQ（s, t） has more attractive properties than other variations of the fundamental hypercube in terms of fewer edges, lower cost factor and smaller diameter. In this paper, we study the embedding of paths of distinct lengths between any two different vertices in ECQ（s, t）. We prove the result in ECQ（s, t）： if s≥3, t≥3, for any two different vertices, all paths whose lengths are between max{9,「s＋1/2」 ＋「t＋1/2＋4}and 2s＋t＋1？1 can be embedded between the two vertices with dilation 1. Note that the diameter of ECQ（s, t） is「s＋1/2 」＋「t＋1/2 」＋2. The obtained result is optimal in the sense that the dilations of path embeddings are all 1. The result reveals the fact that ECQ（s, t） preserves the path embedding capability to a large extent, while it only has about one half edges of CQn.
