Profile minimization on products of graphs

The profile minimization problem arose from the study of sparse matrix technique. In terms of graphs, the problem is to determine the profile of a graph G which is defined asP(G)=minf∑v∈V(G)maxx∈N[v](f(v)-f(x)),where f   runs over all bijections from V(G)V(G) to {1,2,…,|V(G)|}{1,2,…,|V(G)|} and N[v]={v}∪{x∈V(G):xv∈E(G)}N[v]={v}∪{x∈V(G):xv∈E(G)}. The main result of this paper is to determine the profiles of Km×KnKm×Kn, Ks,t×KnKs,t×Kn and Pm×KnPm×Kn.