×

Disjoint cycles through prescribed vertices in multidimensional tori. (English) Zbl 07479739

Summary: For a positive integer \(r\), a graph \(G\) is spanning \(r\)-cyclable if for any given set \(F\) of \(r\) vertices, there exists \(r\) vertex-disjoint cycles that together span \(G\) and each cycle contains exactly one vertex from \(F\). It is known that the hypercube \(Q_{n}\) and its variation, the crossed cube, are spanning \(r\)-cyclable for \(1 \leq r \leq n-1\). We prove that every \(n\)-dimensional torus, different from \(C_{3} \square C_{3}\), is spanning \(r\)-cyclable for \(1 \leq r \leq 2n-1\).

MSC:

05C38 Paths and cycles
PDFBibTeX XMLCite
Full Text: Link

References:

[1] V. Batagelj and T. Pisanski, Hamiltonian cycles in the Cartesian product of a tree and a cycle, Discrete Math., 38 (1982) 311-312. · Zbl 0472.05042
[2] S. Chiba and T. Yamashita, Degree conditions for the existence of vertex-disjoint cycles and paths: A Survey, Graphs Combin., 34 (2018) 1-83. · Zbl 1382.05017
[3] K. Corr´adi and A. Hajnal, On the maximal number of independent circuits in graph, Acta Math. Acad. Sci. Hungar., 14 (1963) 423-439. · Zbl 0118.19001
[4] Y. Egawa, H. Enomoto, R. Faudree, H. Li and I. Schiermeyer, Two-factors each component of which contains a specified vertex, J. Graph Theory, 43 (2003) 188-198. · Zbl 1024.05073
[5] R. Gould, Recent advances on the Hamiltonian problem: Survey III, Graphs Combin., 30 (2003) 1-46. · Zbl 1292.05163
[6] R. Gould, A look at cycles containing specified elements of a graph, Discrete Math., 309 (2009) 6299-6311. · Zbl 1229.05169
[7] Y. Ishigami and T. Jiang, Vertex-disjoint cycles containing prescribed vertices, J. Graph Theory, 42 (2003) 276-296. · Zbl 1017.05058
[8] H. Kim and J. Park, Paths and cycles in d-dimensional tori with faults, in Proc. of Workshop on Algorithms and Computation WAAC’01, Pusan, Korea (2001) 67-74.
[9] T. Kung, C. Hung, C. Lin, H. Chen, C. Lin and L. Hsu, A Framework of cycle-based clustering on the crossed cube architecture, 2016 10th International Conference on Innovative Mobile and Internet Services in Ubiquitous Computing (IMIS), Fukuoka, 1 (2016) 430-434.
[10] F. Leighton, Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes, M. Kaufmann Publishers Inc., San Mateo, California (1992). · Zbl 0743.68007
[11] C. Lin, J. Tana, L. Hsu and T. Kung, Disjoint cycles in hypercubes with prescribed vertices in each cycle, Discrete Appl. Math., 161 (2013) 2992-3004. · Zbl 1287.05072
[12] S. Mane and B. Waphare, Regular connected bipancyclic spanning subgraphs of hypercubes, Comput. Math. Appl., 62(9) (2011) 3551-3554 · Zbl 1235.05076
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.