Abstract
In this paper, we introduce two kinds of graphs: the generalized matching networks (GMNs) and the recursive generalized matching networks (RGMNs). The former generalize the hypercube-like networks (HLNs), 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 -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.
Acknowledgements
The authors are grateful to the two anonymous reviewers for their valuable comments that have improved the quality of this paper. This work was supported by New Century Excellent Talent Funds of Educational Ministry of China (NCET-05-0759), Doctorate Funds of Educational Ministry of China (20050611001), and Natural Science Funds of Chongqing (2006BB2231, 2005BB2191).