Matchings Extend to Perfect Matchings on Hypercube Networks
| Autor: | 李坤龍 |
|---|---|
| Rok vydání: | 2010 |
| Druh dokumentu: | 學位論文 ; thesis |
| Popis: | 98 The underlying topology of an interconnection network is usually modeled as a graph G = (V, E), in which V is the vertex set and E is the edge set. A matching M in graph G is a set of pairwise non-adjacent edges. Every vertex is incident with at most one edge of M. A perfect matching is a matching which matches all vertices of the graph. The hypercube is a popular network and it has been widely used in parallel systems, including regularity, symmetry, small diameter, strong connectivity, recursive construction, partition ability, relatively low link complexity, easy routing and broadcasting algorithms. 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 M with at most n – 1 edges, it can be extended to a perfect matching of Qn for n >= 1. Furthermore, we show that for any arbitrary non-forbidden matching M with m = n edges in the hypercube Qn for n >= 1, it can be extended to a perfect matching of Qn. 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 may lead 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, n >= 2. |
| Databáze: | Networked Digital Library of Theses & Dissertations |
| Externí odkaz: |
|