JISE Vol.24 No.2 #19

Journal of Information Science and Engineering, Vol. 24 No. 2, pp. 615-625 (March 2008)

Hamiltonian Connectivity, Pancyclicity and 3^*-Connectivity of Matching Composition Networks^*

Shin-Shin Kao, Jui-Chia Wu and Yuan-Kang Shih¹
Department of Applied Mathematics
Chung Yuan Christian University
Chungli, 320 Taiwan
E-mail: skao@math.cycu.edu.tw
¹Department of Computer Science
National Chiao Tung University
Hsinchu, 300 Taiwan

In this paper, we discuss many properties of graphs of Matching Composition Networks (MCN) [16]. A graph in MCN is obtained from the disjoint union of two graphs G₀ and G₁ by adding a perfect matching between V(G₀) and V(G₁). We prove that any graph in MCN preserves the hamiltonian connectivity or hamiltonian laceability, and pancyclicity of G₀ and G₁ under simple conditions. In addition, if there exist three internally vertex-disjoint paths between any pair of distinct vertices in G_i 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 Q_n, the Crossed cube CQ_n, the Twisted cube TQ_n, the Mobius cube MQ_n, and the Hypbercube-like graphs HL_n, our results apply to all of the above-mentioned networks.

Keywords: hypercube-like graphs, perfect matching, hamiltonian-connected, pancyclic, 3*-connected

Retrieve PDF document (200803_19.pdf)

Received March 9, 2006; revised June 22, 2006; accepted October 18, 2006.
Communicated by Tsan-sheng Hsu.
^* This work was supported in part by the National Science Council of Taiwan, R.O.C., under contract No. NSC 94-2115-M-033-006 and NSC 95-2115-M-033-002.