Previous 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20


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 Shih1
Department of Applied Mathematics
Chung Yuan Christian University
Chungli, 320 Taiwan
1Department 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 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 pancyclicity 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 Mobius cube MQn, and the Hypbercube-like graphs HLn, our results apply to all of the above-mentioned networks.

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

Full Text () 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.