Maximizing the number of edges in optimal k-rankings
Review articleOpen access
2015/07/01 Full-length article DOI: 10.1016/j.akcej.2015.06.005
Journal: AKCE International Journal of Graphs and Combinatorics
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