Thumbnail
Access Restriction
Open

Author Chen, Y.-Chuang ♦ Li, Kun-Lung
Source CiteSeerX
Content type Text
File Format PDF
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Perfect Matchings ♦ Hypercube Network ♦ Hamiltonian Cycle ♦ Arbitrary Non-forbidden Matching ♦ Perfect Matching ♦ Prescribed Matchings ♦ Arbitrary Matching ♦ Following Contribution ♦ N-dimensional Hypercube Qn ♦ Arbitrary Perfect Matching ♦ N-dimensional Hypercube Network Qn
Abstract Abstract—In this work, we investigate in the problem of perfect matchings with prescribed matchings in the n-dimensional hypercube network Qn. We obtain the following contributions: For any arbitrary matching with at most n − 1 edges, it can be extended to a perfect matching of Qn for n ≥ 1. Furthermore, for any arbitrary non-forbidden matching with n edges, it also can be extended to a perfect matching of Qn for n ≥ 1. It is shown by J. Fink in 2007 that any arbitrary perfect matching of the n-dimensional hypercube Qn, n ≥ 2, can be extended to a Hamiltonian cycle. Therefore, it leads to a further result that for any arbitrary non-forbidden matching with at most n edges, it can be extended to a Hamiltonian cycle of Qn for n ≥ 2.
Educational Role Student ♦ Teacher
Age Range above 22 year
Educational Use Research
Education Level UG and PG ♦ Career/Technical Study