# Prime labelling of graphs

A prime labeling of a graph is an injective function $f: V(G) \to \{1, 2, ..., |V(G)|\}$ such that for every pair of adjacent vertices $u$ and $v$, $\text{gcd}(f(u), f(v)) = 1$ (labels of any two adjacent vertices are relatively prime).

What can prime labeling be useful for? I was thinking of any applications like scheduling etc. but I'm not sure.

A somewhat fanciful "application."

Suppose nodes represent museum guard stations, and arcs represent lines of sight between stations. The labels represent shift hours: hours at one station before a guard is replaced by a fresh guard.

Then a prime labeling ensures that when there is a change of guard at one station, there is not simultaneously a change of guard at all the adjacent stations, until the lcm of the labels in the neighborhood is reached. So those guard(s) can monitor the change and ensure coverage.

This schedule fails at $t=2 \cdot 3 \cdot 5 = 30$, when no guard covers $B$.

Alternatively, the nodes can represent employees and the arcs employees with similar skills, so again when a shift change occurs, the skill set is covered during the switch.

• (Thanks to @Waldemar for an earlier correction.) Dec 22, 2014 at 17:51
• This is quite fanciful--it seems the museum would be better served if all shifts had the same lengths and staggered start times. Then at most one post would be empty at any time. Dec 22, 2014 at 17:57
• @DanielLitt: Ha! Point taken. But in this museum, all galleries open simultaneously at 9:00AM. :-) Dec 23, 2014 at 0:01
• @JosephO'Rourke thanks a lot! but I don't get why "This schedule fails at t = 30". so prime labelling isn't that perfect for this kind of tasks? :( Jan 6, 2015 at 21:03
• @MarcAndreson: At $t=30$, the guards change at $A,X,C$, so no staying-guard has line-of-sight to the guard change happening at $B$, putting the paintings near $B$ at risk. Jan 6, 2015 at 21:54