L(2,1) L ( 2 , 1 ) -labelling of generalized prisms
In this paper we deal with upper bounds on the ? ? -number of graphs of the form G?K2 G ? K 2 , where ? ? is one of the standard graph productsthe direct, Cartesian, strong, and the lexicographic product. L(2,1) L ( 2 , 1 ) -labelling of products of graphs has been investigated by a number of authors, especially in connection with the well-known conjecture ?(G)?(?(G))2 ? ( G ) ? ( ? ( G ) ) 2 , where ?(G) ? ( G ) is the maximum degree of a graph G G . Up to some degenerate cases, this conjecture was verified for the Cartesian and the lexicographic product by Shao and Yeh (2005)[13], and for the direct and the strong product by Klavar and pacapan (2006)[10] and by Shao etal. (2008)[12]. 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 G?K2 G ? K 2 for the standard products mentioned above, with the role of the maximum degree taken over by the ? ? -number of the graph G G . Methods include lifts along graph covering projections and labellings of M M -sums constructed by Georges and Mauro (2002)[2]. In most cases, our upper bounds are tighter than those currently known.
1 ) covering projection l(2 1) l ( 2 1 ) -labelling l(2 1 ) l(2 1 ) l ( 2 graph product