کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
419377 | 683793 | 2013 | 13 صفحه PDF | دانلود رایگان |
A graph GG is spanning rr-cyclable of order tt if for any rr nonempty mutually disjoint vertex subsets A1,A2,…,ArA1,A2,…,Ar of GG with |A1∪A2∪⋯∪Ar|≤t|A1∪A2∪⋯∪Ar|≤t, there exist rr disjoint cycles C1,C2,…,CrC1,C2,…,Cr of GG such that C1∪C2∪⋯∪CrC1∪C2∪⋯∪Cr spans GG, and CiCi contains AiAi for every ii. In this paper, we prove that the nn-dimensional hypercube QnQn is spanning 2-cyclable of order n−1n−1 for n≥3n≥3. Moreover, QnQn is spanning kk-cyclable of order kk if k≤n−1k≤n−1 for n≥2n≥2. The spanning rr-cyclability of a graph GG is the maximum integer tt such that GG is spanning rr-cyclable of order kk for k=r,r+1,…,tk=r,r+1,…,t but is not spanning rr-cyclable of order t+1t+1. We also show that the spanning 2-cyclability of QnQn is n−1n−1 for n≥3n≥3.
Journal: Discrete Applied Mathematics - Volume 161, Issue 18, December 2013, Pages 2992–3004