7
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ Entertaining mathematicians... Cubic lattices were considered in mathoverflow.net/questions/162173 $\endgroup$
    – user25199
    Commented Dec 23, 2014 at 8:42

1 Answer 1

Reset to default
8
$\begingroup$

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.

PrimeGraph
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.

Improve this answer
$\endgroup$
5
  • $\begingroup$ (Thanks to @Waldemar for an earlier correction.) $\endgroup$
    – Joseph O'Rourke
    Commented Dec 22, 2014 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
    Commented Dec 22, 2014 at 17:57
  • 4
    $\begingroup$ @DanielLitt: Ha! Point taken. But in this museum, all galleries open simultaneously at 9:00AM. :-) $\endgroup$
    – Joseph O'Rourke
    Commented Dec 23, 2014 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
    Commented Jan 6, 2015 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
    Commented Jan 6, 2015 at 21:54

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .