Disjoint cycles in hypercubes with prescribed vertices in each cycle

ASIA unversity > 資訊學院 > 資訊工程學系 > 期刊論文 > Item 310904400/64362

請使用永久網址來引用或連結此文件: http://asiair.asia.edu.tw/ir/handle/310904400/64362

題名:	Disjoint cycles in hypercubes with prescribed vertices in each cycle
作者:	Cheng-Kuan, L;Lin, Cheng-Kuan;Jimmy, J.M.T;Jimmy, J.M.Tan;Hs, Lih-Hsing;Hsu, Lih-Hsing;龔自良;KUNG, TZU-LIANG
貢獻者:	資訊工程學系
關鍵詞:	Spanning cycle, Hamiltonian cycle, Cyclable, Hypercube, Graph
日期:	201308
上傳時間:	2013-10-29 09:41:05 (UTC+0)
摘要:	A graph G is spanning r-cyclable of order t if for any r nonempty mutually disjoint vertex subsets A1,A2,…,Ar of G with \|A1∪A2∪⋯∪Ar\|≤t, there exist r disjoint cycles C1,C2,…,Cr of G such that C1∪C2∪⋯∪Cr spans G, and Ci contains Ai for every i. In this paper, we prove that the n-dimensional hypercube Qn is spanning 2-cyclable of order n−1 for n≥3. Moreover, Qn 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 Qn is n−1 for n≥3.
關聯:	DISCRETE APPLIED MATHEMATICS
顯示於類別:	[資訊工程學系] 期刊論文

文件中的檔案:

檔案	大小	格式	瀏覽次數
index.html	0Kb	HTML	402	檢視/開啟

在ASIAIR中所有的資料項目都受到原著作權保護.