Labeling matched sums with a condition at distance two


Now published - for full text see:

Troxell, D.S.; Adams, S.S. (2011) Labeling matched sums with a condition at distance two. Applied Mathematics Letters Volume, 24(6), 950-957.



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. The lambda number of G is the minimum k over all L(2,1)-labelings of G. Such labelings were introduced as a way of modeling the assignment of frequencies to transmitters operating in close proximity within a communications network. 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 as a way of modeling 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.

Academic Division



Applied Mathematics | Discrete Mathematics and Combinatorics

This document is currently not available here.