Hamiltonian Connectivity, Pancyclicity and 3 * -Connectivity of Matching Composition Networks *
Shin-Shin Kao, Jui-Chia Wu, Yuan-Kang Shih · 2008
In this paper, we discuss many properties of graphs of Matching Composition Net-works (MCN) [16]. A graph in MCN is obtained from the disjoint union of two graphs G0 and G1 by adding a perfect matching between V(G0) and V(G1). We prove that any graph in MCN preserves the hamiltonian connectivity or hamiltonian laceability, and pancyc-licity of G0 and G1 under simple conditions. In addition, if there exist three internally vertex-disjoint paths between any pair of distinct vertices in Gi for i ∈ {0, 1}, then so it is the case in any graph in MCN. Since MCN includes many well-known interconnection networks as special cases, such as the Hypercube Qn, the Crossed cube CQn, the Twisted cube TQn, the Möbius cube MQn, and the Hypbercube-like graphs HLn, our results apply to all of the above-mentioned networks.