The profile of the Cartesian product of graphs

AbstractGiven a graph G, a proper labeling f of G is a one-to-one function from V(G) onto {1,2,…,|V(G)|}. For a proper labeling f of G, the profile width wf(v) of a vertex v is the minimum value of f(v)−f(x), where x belongs to the closed neighborhood of v. The profile of a proper labeling f of G, denoted by Pf(G), is the sum of all the wf(v), where v∈V(G). The profile of G is the minimum value of Pf(G), where f runs over all proper labeling of G. In this paper, we show that if the vertices of a graph G can be ordered to satisfy a special neighborhood property, then so can the graph G×Qn. This can be used to determine the profile of Qn and Km×Qn