Utility And Expandability of Channel Assignments

Abstract

The Channel Assignment Problem is often modeled by integer vertex-labelings of graphs. We will examine \(L(2,1)\)-labelings that realize the span \(\lambda\) of a simple, connected graph \(G = (V, E)\). We define the utility of \(G\) to be the number of possible expansions that can occur on \(G\), where an expansion refers to an opportunity to add a new vertex \(u\) to \(G\), with label \(\lambda(u)\), such that:

1. edges are added between \(u\) and \(v\);
2. edges are added between \(u\) and the neighbors of \(v\); and
3. the resulting labeling of the graph is a valid \(L(2, 1)\)-labeling.

Building upon results of Griggs, Jin, and Yeh, we use known values of \(\lambda\) to compute utility for several infinite families and analyze the utility of specific graphs that are of interest elsewhere.