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.

  • $\begingroup$ (Thanks to @Waldemar for an earlier correction.) $\endgroup$ – Joseph O'Rourke Dec 22 '14 at 17:51
  • 7
    $\begingroup$ 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. $\endgroup$ – Daniel Litt Dec 22 '14 at 17:57
  • 4
    $\begingroup$ @DanielLitt: Ha! Point taken. But in this museum, all galleries open simultaneously at 9:00AM. :-) $\endgroup$ – Joseph O'Rourke Dec 23 '14 at 0:01
  • 1
    $\begingroup$ @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? :( $\endgroup$ – Marc Andreson Jan 6 '15 at 21:03
  • $\begingroup$ @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. $\endgroup$ – Joseph O'Rourke Jan 6 '15 at 21:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.