Header menu link for other important links
X
Induced H-packing k-partition problem in interconnection networks
S maria jesu raja, Antony xavier,
Published in Informa UK Limited
2017
Volume: 2
   
Issue: 4
Pages: 136 - 146
Abstract

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.

About the journal
JournalInternational Journal of Computer Mathematics: Computer Systems Theory
PublisherInforma UK Limited
ISSN2379-9927
Open Access0