کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
429076 687035 2010 5 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Cycles passing through a prescribed path in a hypercube with faulty edges
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Cycles passing through a prescribed path in a hypercube with faulty edges
چکیده انگلیسی

Let Qn denote an n-dimensional hypercube with n⩾2, P be a path of length h in Qn and F⊂E(Qn)\E(P). Recently, Tsai proved that if 1⩽h⩽n−1 and |F|⩽n−1−h, then in the graph Qn−F the path P lies on a cycle of every even length from 2h+2 to n2, and P also lies on a cycle of length 2h if |F|⩽h−2. In this paper, we show that if 1⩽h⩽2n−3 and |F|⩽n−2−⌊h/2⌋, then in Qn−F the path P lies on a cycle of every even length from 2h+2 to n2, and P also lies on a cycle of length 2h if P contains two edges of the same dimension or P is a shortest path and |F∩E(Qh)|⩽h−2, where Qh is the h-dimensional subcube containing the path P. Moreover, the upper bound 2n−3 of h is sharp and the upper bound n−2−⌊h/2⌋ of |F| is sharp for any given h with 1⩽h⩽2n−3.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 110, Issue 16, 31 July 2010, Pages 625-629