-labelling of generalized prisms

Abstract: In this paper we deal with upper bounds on the -number of graphs of the form , where is one of the standard graph products—the direct, Cartesian, strong, and the lexicographic product. -labelling of products of graphs has been investigated by a number of authors, especially in connection with the well-known conjecture , where is the maximum degree of a graph . Up to some degenerate cases, this conjecture was verified for the Cartesian and the lexicographic product by Shao and Yeh (2005) , and for the direct and the strong product by Klavžar and Špacapan (2006)  and by Shao et al. (2008) . If one of the factors of the Cartesian or the direct product has maximum degree one, only higher upper bounds than the one following from the conjecture are currently known. We derive alternative upper bounds on the -number of graphs for the standard products mentioned above, with the role of the maximum degree taken over by the -number of the graph . Methods include lifts along graph covering projections and labellings of -sums constructed by Georges and Mauro (2002) . In most cases, our upper bounds are tighter than those currently known. [Copyright &y& Elsevier]