Disjoint cycles in hypercubes with prescribed vertices in each cycle

ASIAIR > College of Computer Science > Department of Computer Science and Information Engineering > Journal Artical > Item 310904400/79214

Please use this identifier to cite or link to this item: http://asiair.asia.edu.tw/ir/handle/310904400/79214

Title:	Disjoint cycles in hypercubes with prescribed vertices in each cycle
Authors:	Cheng-Kuan, L;Lin, Cheng-Kuan;Jimmy, J.M.T;Jimmy, J.M.Tan;Hs, Lih-Hsing;Hsu, Lih-Hsing;龔自良;KUNG, TZU-LIANG
Contributors:	資訊工程學系
Date:	201312
Issue Date:	2014-01-06 12:23:07 (UTC+0)
Abstract:	A graph G is spanning r-cyclable of order t if for any r nonempty mutually disjoint vertex subsets A"1,A"2,...,A"r of G with \|A"1@?A"2@?...@?A"r\|@?t, there exist r disjoint cycles C"1,C"2,...,C"r of G such that C"1@?C"2@?...@?C"r spans G, and C"i contains A"i for every i. In this paper, we prove that the n-dimensional hypercube Q"n is spanning 2-cyclable of order n-1 for n>=3. Moreover, Q"n is spanning k-cyclable of order k if k@?n-1 for n>=2. The spanning r-cyclability of a graph G is the maximum integer t such that G is spanning r-cyclable of order k for k=r,r+1,...,t but is not spanning r-cyclable of order t+1. We also show that the spanning 2-cyclability of Q"n is n-1 for n>=3.
Relation:	DISCRETE APPLIED MATHEMATICS, 161(18):2992-3004.
Appears in Collections:	[Department of Computer Science and Information Engineering] Journal Artical

Files in This Item:

File	Size	Format
index.html	0Kb	HTML	537	View/Open