Distributing the overall workload evenly among a set of processors in VLSI designs to achieve high speed-ups in computation has been widely studied as a graph partitioning problem. Determining induced matching k-partition number even when k = 2 is an NP-complete problem. In this paper we deal with the induced matching partition for Petersen graphs and circulant graphs and determine their induced matching partition numbers. © 2013 The Authors. Published by Elsevier Ltd.

Indra Rajasingh

Mathematics

School of Advanced Sciences

Chennai Campus

Shanthi A.S

Fulltext

Vellore Institute of Technology (VIT) is a private university located in&nbsp;Tamil Nadu, India. Founded in 1984, as Vellore Engineering College, the institution offers 20 undergraduate, 34 postgraduate, four integrated and four research programs. It has campuses in Vellore, Amravati, Bhopal and Chennai.

VIT is one of the top ranked private universities in India according to NIRF, THE and QS Rankings.&nbsp;Govt. of India has recognized&nbsp;VIT, Vellore as an&nbsp;Institution of Eminence. This has allowed VIT to take independent quality initiatives and move up in world ranking.

&nbsp;

&nbsp;

VIT University

Procedia Engineering

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 &amp; Francis Group.

International Journal of Computer Mathematics: Computer Systems Theory

Induced H-packing k-partition problem in interconnection networks

Induced Matching Partition of Petersen and Circulant Graphs

Informatics Engineering and Information Science Communications in Computer and Information Science

Journal	Data powered by TypesetProcedia Engineering
Publisher	Data powered by TypesetElsevier BV
ISSN	1877-7058
Open Access	Yes