Maximizing the number of edges in optimal k-rankings

Abstract

A 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.

Keywords

• Coloring
• Minimum k-ranking
• Maximum number of edges