Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6872182 | Discrete Applied Mathematics | 2014 | 8 Pages |
Abstract
The spectrum allocation problem in wireless communications 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. One well-known model is the L(2,1)-labeling of a graph G in which a function f maps the vertices of G to the nonnegative integers such that if vertices x and y are adjacent, then |f(x)âf(y)|â¥2, and if x and y are at distance two, then |f(x)âf(y)|â¥1. The λ-number of G is the minimum span over all L(2,1)-labelings of G. Informally, an amalgamation of two graphs G1 and G2 along a fixed graph G0 is the simple graph obtained by identifying the vertices of two induced subgraphs isomorphic to G0, one in G1 and the other in G2. In this work, we supply a tight upper bound for the λ-number of amalgamations of several Cartesian products of complete graphs along a complete graph and find the exact λ-numbers for certain infinite subclasses of amalgamations of this form. A surprising relationship between the former upper bound and the minimum makespan scheduling problem is highlighted.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Nathaniel Karst, Jessica Oehrlein, Denise Sakai Troxell, Junjie Zhu,