Pivot labellings are temporal graph labellings in which one distinguished vertex $r$ acts as a temporal hub: all vertices can reach $r$ by some time $t$, and $r$ can reach all vertices after time $t$.

A pivot labelling gives a particularly structured labelling that is temporally connected: all reachabilities are certifiable through one common pivot vertex $r$.

Definition

Let $\mathcal G=(G,\lambda)$ be a temporal graph and let $r\in V(G)$. We say that $\lambda$ is a pivot labelling with pivot $r$ if there exists a time $\tau$ such that:

1. for every vertex $v\in V(G)$, there is a temporal path from $v$ to $r$ arriving at time at most $\tau$, and
2. for every vertex $v\in V(G)$, there is a temporal path from $r$ to $v$ whose first edge is used at time at least $\tau$.

The time $\tau$ is called a pivot time for $r$.

Tree construction

Given a rooted spanning tree $T$ with root $r$, one can create a pivot-style labelling by assigning:

• decreasing labels toward the root;
• larger increasing labels away from the root.