A note on Hamiltonian paths and cycles with prescribed edges in the 3-ary n-cube

作者：Yang, Yuxing; Wang, Shiying^*

来源：Information Sciences, 2015, 296: 42-45.

DOI：10.1016/j.ins.2014.10.034

• Parallel system
• Interconnection network
• 3-Ary n-cube
• Hamiltonian path
• Hamiltonian cycle

In Wang et al. (2011), the authors proved that the 3-ary n-cube admits a Hamiltonian path between u and v passing through every edges in a prescribed set P with at most 2n - 2 edges if the subgraph induced by P consists of pairwise vertex-disjoint paths, none of which has u or vas internal vertices or both of them as end-vertices. They proved the above results based on some Lemmas including Lemma 4.7 in the paper. However, the proof of Case 2.4 of Lemma 4.7 is incorrect. In this note, we will give a counterexample and provide a correct proof. Therefore, the main result in the above paper is still correct.

• 出版日期2015-3-1
• 单位山西大学; 河南师范大学