JISE


  [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


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 
E-mail: skao@math.cycu.edu.tw 
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 fori {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

  Retrieve PDF document (JISE_200802_19.pdf)