Labeling matched sums with a condition at distance two

An L ( 2 , 1 ) -labeling of a graph G is a function f : V ( G ) → { 0 , 1 , … , k } such that | f ( x ) − f ( y ) | ≥ 2 if x and y are adjacent vertices, and | f ( x ) − f ( y ) | ≥ 1 if x and y are at distance 2. Such labelings were introduced as a way of modeling the assignment of frequencies to transmitters operating in close proximity within a communications network. The lambda number of G is the minimum k over all L ( 2 , 1 ) -labelings of G . This paper considers the lambda number of the matched sum of two same-order disjoint graphs, wherein the graphs have been connected by a perfect matching between the two vertex sets. Matched sums have been studied in this context to model possible connections between two different networks with the same number of transmitters. We completely determine the lambda number of matched sums where one of the graphs is a complete graph or a complete graph minus an edge. We conclude by discussing some difficulties that are encountered when trying to generalize this problem by removing more edges from a complete graph.