##### Maximizing the number of edges in optimal k-rankings

Review articleOpen access###### Rigoberto Flórez - No affiliation found

**2015/07/01**DOI: 10.1016/j.akcej.2015.06.005

*Full-length article***Journal:**AKCE International Journal of Graphs and Combinatorics

##### Abstract:

AbstractA k-ranking is a vertex k-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 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=P2k−1, C2k, Km1,m2,…,mt, and the union of two copies of Kn 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.

Request full text