On the L(2,1)L(2,1)-labelings of amalgamations of graphs

The problem of assigning frequencies to transmitters in a radio network can be modeled through vertex labelings of a graph, wherein each vertex represents a transmitter and edges connect vertices whose corresponding transmitters are operating in close proximity. In one such model, an L(2,1)L(2,1)-labeling of a graph G is employed, which is an assignment fof nonnegative integers to the vertices of G such that if vertices x and y   are adjacent, |f(x)−f(y)|≥2|f(x)−f(y)|≥2, and if x and y   are at distance two, |f(x)−f(y)|≥1|f(x)−f(y)|≥1. The λλ-number of G   is the minimum span over all L(2,1)L(2,1)-labelings of G. Informally, an amalgamation   of two graphs G1G1 and G2G2 along a fixed graph G0G0 is the simple graph obtained by identifying the vertices of two induced subgraphs isomorphic to G0G0, one of G1G1 and the other of G2G2. We provide upper bounds for the λλ-number of the amalgamation of graphs along a given graph by determining the exact λλ-number of amalgamations of complete graphs along a complete graph. We also provide the exact λλ-numbers of amalgamations of rectangular grids along a path, or more specifically, of the Cartesian products of a path and a star with spokes of arbitrary lengths.