Get all the updates for this publication
The induced matching k-partition number of a graph G, denoted by imp(G), is the minimum integer k such that V(G) has a k-partition {V1, V2, . . . , Vk} where for each i, 1 ≤ i ≤ k, G[Vi], the subgraph of G induced by Vi, 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 ipp(G, H). We prove that the induced P3-packing k-partition problem and induced C4-packing k-partition problem are both NP-complete problems. We obtain the induced P3-packing k-partition number for sierpiński graphs and hypercube networks. Further we determine the induced C4-packing k-partition number for hypercube networks. © 2017, © 2017 Informa UK Limited, trading as Taylor & Francis Group.
View more info for "Induced H-packing k-partition problem in interconnection networks"
Journal | International Journal of Computer Mathematics: Computer Systems Theory |
---|---|
Publisher | Informa UK Limited |
ISSN | 2379-9927 |
Open Access | 0 |