標題: Disjoint cycles in hypercubes with prescribed vertices in each cycle
作者: Lin, Cheng-Kuan
Tan, Jimmy J. M.
Hsu, Lih-Hsing
Kung, Tzu-Liang
資訊工程學系
Department of Computer Science
關鍵字: Spanning cycle;Hamiltonian cycle;Cyclable;Hypercube;Graph
公開日期: 1-十二月-2013
摘要: 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 vertical bar A(1) boolean OR A(2) boolean OR ... boolean OR A(r)vertical bar <= t, there exist r disjoint cycles C-1, C-2,...,Cr of G such that C-1 boolean OR C-2 boolean OR ... C-r spans G, and C-t 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 - for n >= 3. (C) 2013 Elsevier B.V. All rights reserved.
URI: http://dx.doi.org/10.1016/j.dam.2013.07.004
http://hdl.handle.net/11536/23211
ISSN: 0166-218X
DOI: 10.1016/j.dam.2013.07.004
期刊: DISCRETE APPLIED MATHEMATICS
Volume: 161
Issue: 18
起始頁: 2992
結束頁: 3004
顯示於類別:期刊論文


文件中的檔案:

  1. 000328235600021.pdf