Originators: Griggs, Jin, Yeh, Bahls (presented by T. Mahoney - REGS 2010)
Definitions:
An L(2,1)-labeling of a simple connected graph G, is a function
l: V(G) → {0,1,2,...} such that |l(u)-l(v)|≥2
whenever u,v ∈ V(G) are adjacent, and |l(u)-l(v)| ≥1
and whenever the distance between u and v is 2. The span
of a labeling is the difference between the largest and smallest values used,
and λ(G) is the minimum span of an L(2,1)-labeling of
G. This concept was introduced by Griggs & Yeh [GY] (see also [CK]).
Calamoneri [C] surveyed one family of generalizations.
Bahls and Mahoney [BM] introduced a measure of the flexibility in optimal L(2,1)-labelings. The utility of an L(2,1)-labeling l of a graph G, written U(G,l), is the number of vertices u∈V(G) such that l extends to an L(2,1)-labeling of the graph obtained from G by adding a vertex with the same neighborhood as u. There is no requirement that these vertices permit expansions simultaneously. The utility of the graph G, written U(G), is the maximum of U(G,l) over L(2,1)-labelings with minimum span.
The vertices at which an L(2,1)-labeling can be expanded are characterized as follows: a vertex u is counted by U(G,l) if and only if l(u) can be changed by at least 2 to obtain another valid L(2,1)-labeling.
Examples: Graphs with utility 0 include complete graphs, complete k-partite graphs, wheels, cycles, ladders, and infinite regular lattices. A path with n vertices has utility 0 if n≤5, 1 if 7≤n<10, and 2 if n≥10 or n=6. The cartesian product of a cycle with an edge has utility 0 if n<10 or n≡0 (mod 3), and it has utility ⌊n/3 - 2⌋ if n≥10 and n is not divisible by 3.
Question 1:
What is the largest utility of a graph with n vertices?
Comments: A graph with utility n-4 is known, and it is known that every n-vertex graph has utility at most n-1.
Question 2:
What is the utility of the n-dimensional hypercube Qn?
References:
[BM] P. Bahls and T. Mahoney, "Utility and Expandability of Channel
Assignments," Ars Combinatoria, (In Press),
preprint.
[C] T. Calamoneri, "The L(h, k)-labelling problem: A survey and annotated
bibliography," The Computer Journal, 49 (2006) no. 5, 585-608.
[CK] G. Chang and D. Kuo, "The L(2, 1)-labeling problem on graphs," SIAM J.
Discrete Math, 9 (1996) no. 2, 309-316.
[GY] J. Griggs and R. Yeh, "Labelling graphs with a condition at distance
2," SIAM J. Disc. Math 5 (1992) no. 4, 586-595.