Minimizing the Number of Exceptional Edges in Cellular Manufacturing Problem

The input for a cellular manufacturing problem consists of a set X of m machines, a set Y of p   parts and an m×pm×p matrix A=(aij)A=(aij), where aij=1aij=1 or 0 according as the part pjpj is processed on the machine mimi. This data can be represented as a bipartite graph with bipartition X, Y   where mimi is joined to pjpj if aij=1aij=1. Given a partition π   of V(G)V(G) into k   subsets V1,V2,...,VkV1,V2,...,Vk such that |Vi|≥2|Vi|≥2 and the induced subgraph 〈V〉〈V〉 is connected, any edge of G   with one end in ViVi and other end in VjVj with i≠ji≠j, is called an exceptional edges. The cellular manufacturing problem is to find a partition π   with minimum number of exceptional edge. In this paper we determine this number for the subdivision graph of Kn,Km,nKn,Km,n and the wheel WnWn.