Induced H-packing k-partition problem in interconnection networks. Issue 4 (2nd October 2017) - Maria Jesu Raja, S.; Xavier, Antony; Rajasingh, Indra
ABSTRACT: The induced matching k -partition number of a graph G, denoted by, is the minimum integer k such that has a k -partition where for each i, , , the subgraph of G induced by, is a 1-regular graph. The induced matching k -partition problem is NP -complete even for k = 2. In this paper we extend the concept of matching to H -packing and denote the minimum induced H -packing k -partition number as . We prove that the induced -packing k -partition problem and induced -packing k -partition problem are both NP -complete problems. We obtain the induced -packing k -partition number for sierpiński graphs and hypercube networks. Further we determine the induced -packing k -partition number for hypercube networks.