Induced H-packing k-partition problem in interconnection networks. Issue 4 (2nd October 2017)

• Record Type: Journal Article
• Authors: Maria Jesu Raja, S.; Xavier, Antony; Rajasingh, Indra
• Is Part Of: International journal of computer mathematics. Volume 2:Issue 4(2017)
• Page Start: 136
• Page End: 146
• Publication Date: 2017-10-02
• Subjects: Almost perfect -packing -- perfect -packing -- induced H-packing k-partition -- NP-completeness -- hypercube networks; 05C70; Computer systems -- Periodicals; Computer systems; Periodicals; 004
• DOI: 10.1080/23799927.2017.1383941
• Languages: English
• ISSNs: 2379-9927

Abstract

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.