کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
394550 665812 2013 12 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On the mutually independent Hamiltonian cycles in faulty hypercubes
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر هوش مصنوعی
پیش نمایش صفحه اول مقاله
On the mutually independent Hamiltonian cycles in faulty hypercubes
چکیده انگلیسی

Two ordered Hamiltonian paths in the n-dimensional hypercube Qn are said to be independent if ith vertices of the paths are distinct for every 1 ⩽ i ⩽ 2n. Similarly, two s-starting Hamiltonian cycles are independent if the ith vertices of the cycle are distinct for every 2 ⩽ i ⩽ 2n. A set S of Hamiltonian paths (s-starting Hamiltonian cycles) are mutually independent if every two paths (cycles, respectively) from S are independent. We show that for n pairs of adjacent vertices wi and bi, there are n mutually independent Hamiltonian paths with endvertices wi, bi in Qn. We also show that Qn contains n − f fault-free mutually independent s-starting Hamiltonian cycles, for every set of f ⩽ n − 2 faulty edges in Qn and every vertex s. This improves previously known results on the numbers of mutually independent Hamiltonian paths and cycles in the hypercube with faulty edges.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Sciences - Volume 236, 1 July 2013, Pages 224–235
نویسندگان
, , ,