Induced Matching Partition of Petersen and Circulant Graphs

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.