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⋆K2G⋆K2, where ⋆⋆ is one of the standard graph products—the 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 GG. 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 Klavžar and Špacapan (2006) [10] and by Shao et al. (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⋆K2G⋆K2 for the standard products mentioned above, with the role of the maximum degree taken over by the λλ-number of the graph GG. Methods include lifts along graph covering projections and labellings of MM-sums constructed by Georges and Mauro (2002) [2]. In most cases, our upper bounds are tighter than those currently known.

► We study λλ-numbers of graphs of the form G⋆K2G⋆K2 where ⋆⋆ is a standard graph product.
► We improve an upper bound on the λλ-number of the direct product G×K2G×K2 by a constant.
► We give a new upper bound on the λλ-number of the Cartesian product G□K2.
► We identify an error in proof of Theorem 2.3 in [Discrete Math. 259 (2002), 311–318].
► We improve an upper bound on the λλ-number of the strong product G⊠K2G⊠K2 by a polynomial.