کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
428330 686637 2007 5 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Path bipancyclicity of hypercubes
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Path bipancyclicity of hypercubes
چکیده انگلیسی

A bipartite graph is vertex-bipancyclic (respectively, edge-bipancyclic) if every vertex (respectively, edge) lies in a cycle of every even length from 4 to |V(G)| inclusive. It is easy to see that every connected edge-bipancyclic graph is vertex-bipancyclic. An n-dimensional hypercube, or n-cube denoted by Qn, is well known as bipartite and one of the most efficient networks for parallel computation. In this paper, we study a stronger bipancyclicity of hypercubes. We prove that every n-dimensional hypercube is (2n−4)-path-bipancyclic for n⩾3. That is, for any path P of length k with 1⩽k⩽2n−4 and any integer l with max{2,k}⩽l⩽2n−1, an even cycle C of length 2l can be found in Qn such that the path P is included in C for n⩾3.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 101, Issue 3, 14 February 2007, Pages 93-97