Maximizing the number of edges in optimal kk-rankings

A kk-ranking is a vertex kk-coloring with positive integers 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 kk such that GG has a kk-ranking. For certain graphs GG we consider the maximum number of edges that may be added to GG without changing the rank number. Here we investigate the problem for G=P2k−1G=P2k−1, C2kC2k, Km1,m2,…,mtKm1,m2,…,mt, and the union of two copies of KnKn joined by a single edge. In addition to determining the maximum number of edges that may be added to GG without changing the rank number we provide an explicit characterization of which edges change the rank number when added to GG, and which edges do not.