Path Coverings with Prescribed Ends in Faulty Hypercubes

被引：4

作者：

Castaneda, Nelson ^{[1
]}

Gotchev, Ivan S. ^{[1
]}

机构：

[1] Cent Connecticut State Univ, Dept Math Sci, New Britain, CT 06050 USA

来源：

GRAPHS AND COMBINATORICS | 2015年 / 31卷 / 04期

关键词：

Hypercube; Path covering; Prescribed ends of a path; Hamiltonian path; Hamiltonian cycle; HAMILTONIAN CYCLES; EDGES;

D O I：

10.1007/s00373-014-1426-0

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

We discuss the existence of vertex disjoint path coverings with prescribed ends for the -dimensional hypercube with or without deleted vertices. Depending on the type of the set of deleted vertices and desired properties of the path coverings we establish the minimal integer such that for every such path coverings exist. Using some of these results, for , we prove Locke's conjecture that a hypercube with deleted vertices of each parity is Hamiltonian if Some of our lemmas substantially generalize known results of I. Havel and T. DvoA (TM) ak. At the end of the paper we formulate some conjectures supported by our results.

引用

页码：833 / 869

页数：37

共 50 条

[11] On path bipancyclicity of hypercubes
Chen, Xie-Bin
INFORMATION PROCESSING LETTERS, 2009, 109 (12) : 594 - 598
[12] Hamiltonian cycles in hypercubes With faulty edges
Liu, Jia-Jie
Wang, Yue-Li
INFORMATION SCIENCES, 2014, 256 : 225 - 233
[13] Hamiltonian laceability in hypercubes with faulty edges
Wang, Fan
Zhang, Heping
DISCRETE APPLIED MATHEMATICS, 2018, 236 : 438 - 445
[14] Bipanconnectivity of faulty hypercubes with minimum degree
Sun, Chao-Ming
APPLIED MATHEMATICS AND COMPUTATION, 2012, 218 (09) : 5518 - 5523
[15] Long cycles in hypercubes with distant faulty vertices
Gregor, Petr
Skrekovski, Riste
DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE, 2009, 11 (01): : 185 - 198
[16] Cycles passing through a prescribed path in a hypercube with faulty edges
Chen, Xie-Bin
INFORMATION PROCESSING LETTERS, 2010, 110 (16) : 625 - 629
[17] Cycles in highly faulty hypercubes
Yang, MC
Tan, JJM
Hsu, LH
FCS '05: Proceedings of the 2005 International Conference on Foundations of Computer Science, 2005, : 101 - 107
[18] Many-to-many disjoint paths in faulty hypercubes
Chen, Xie-Bin
INFORMATION SCIENCES, 2009, 179 (18) : 3110 - 3115
[19] Hamiltonian cycles and paths in hypercubes with disjoint faulty edges
Dybizbanski, Janusz
Szepietowski, Andrzej
INFORMATION PROCESSING LETTERS, 2021, 172 (172)
[20] Matchings extend to Hamiltonian cycles in hypercubes with faulty edges
Xie-Bin Chen
Frontiers of Mathematics in China, 2019, 14 : 1117 - 1132

← 1 2 3 4 5 →