Article ID Journal Published Year Pages File Type
419377 Discrete Applied Mathematics 2013 13 Pages PDF
Abstract

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.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, , , ,