Generalized matching networks and their properties. (English) Zbl 1115.68025
Summary: We introduce two kinds of graphs: the Generalized Matching Networks (GMNs) and the recursive generalized matching networks. The former generalize the hypercube-like networks, while the latter include the generalized cubes and the star graphs. We prove that a GMN on a family of \(k\)-connected building graphs is \((k+1)\)-connected. We then prove that a GMN on a family of Hamiltonian-connected building graphs having at least three vertices each is Hamiltonian-connected. Our conclusions generalize some previously known results.
MSC:
| 68M10 | Network design and communication in computer systems |
Keywords:
interconnection network; generalized matching network; recursive generalized matching network; connectivity; Hamiltonian connectednessReferences:
| [1] | DOI: 10.1016/0743-7315(91)90113-N · doi:10.1016/0743-7315(91)90113-N |
| [2] | Akers, S.B., Harel, D. and Krishnamurthy, B. The star graph: an attractive alternative to then-cube. Proceedings of International Conference of Parallel Processing. pp.393–400. |
| [3] | DOI: 10.1109/12.21148 · Zbl 0678.94026 · doi:10.1109/12.21148 |
| [4] | Bondy J.A., Graph Theory with Applications (1976) · Zbl 1226.05083 |
| [5] | DOI: 10.1016/S0096-3003(02)00223-0 · Zbl 1025.05037 · doi:10.1016/S0096-3003(02)00223-0 |
| [6] | DOI: 10.1109/12.381950 · Zbl 1041.68522 · doi:10.1109/12.381950 |
| [7] | DOI: 10.1109/71.159036 · doi:10.1109/71.159036 |
| [8] | Fan J., Chinese Journal of Computers 26 pp 84– (2003) |
| [9] | DOI: 10.1109/TC.2005.33 · doi:10.1109/TC.2005.33 |
| [10] | DOI: 10.1109/TC.2004.50 · doi:10.1109/TC.2004.50 |
| [11] | Parhami B., An Introduction to Parallel Processing: Algorithms and Architectures (1999) |
| [12] | DOI: 10.1016/j.jpdc.2005.05.002 · Zbl 1101.68349 · doi:10.1016/j.jpdc.2005.05.002 |
| [13] | DOI: 10.1016/j.ipl.2005.05.009 · Zbl 1185.68046 · doi:10.1016/j.ipl.2005.05.009 |
| [14] | DOI: 10.1016/j.ipl.2004.03.009 · Zbl 1178.68043 · doi:10.1016/j.ipl.2004.03.009 |
| [15] | DOI: 10.1109/SPDP.1993.395450 · doi:10.1109/SPDP.1993.395450 |
| [16] | Yang X., Information Processing Letters 97 pp 88– (2006) |
| [17] | DOI: 10.1080/0020716042000301752 · Zbl 1097.68522 · doi:10.1080/0020716042000301752 |
| [18] | DOI: 10.1016/j.amc.2005.11.080 · Zbl 1110.68115 · doi:10.1016/j.amc.2005.11.080 |
| [19] | DOI: 10.1016/j.aml.2003.10.009 · Zbl 1056.05074 · doi:10.1016/j.aml.2003.10.009 |
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.
