Maximizing the number of edges in optimal k-rankings
Review articleOpen access
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

References (0)

Cited By (0)

No reference data.
No citation data.
Advertisement
Join Copernicus Academic and get access to over 12 million papers authored by 7+ million academics.
Join for free!