Maximizing the number of edges in optimal k-rankings

AKCE International Journal of Graphs and Combinatorics

Rigoberto Flórez¹  Darren A. Narayan² 

[1] Department of Mathematics and Computer Science, The Citadel, Charleston, SC 29409, United States;School of Mathematical Sciences, Rochester Institute of Technology, Rochester, NY 14623-5604, United States;

关键词: Coloring;    Minimum k-ranking;    Maximum number of edges;   

DOI  :  10.1016/j.akcej.2015.06.005

来源: DOAJ

【 摘 要 】

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.

【 授权许可】

Unknown