  A $k$-ranking is a vertex $k$-coloring such that if two vertices have the
same color any path connecting them contains a vertex of larger color. The rank
number of a graph is smallest $k$ such that $G$ has a $k$-ranking. For certain
graphs $G$ we consider the maximum number of edges that may be added to $G$
without changing the rank number. Here we investigate the problem for
$G=P_{2^{k-1}}$, $C_{2^{k}}$, $K_{m_{1},m_{2},\dots,m_{t}}$, and the union of
two copies of $K_{n}$ joined by a single edge. In addition to determining the
maximum number of edges that may be added to $G$ without changing the rank
number we provide an explicit characterization of which edges change the rank
number when added to $G$, and which edges do not.
