Minimal !-rankings and the a-rank number of a path
Ajay Narayan, Victoria A. Shults · Discrete Mathematics · 2003
Given a graph af unction# : $ (!) !f 12%%%&g is a &-ranking of ! if #(' )= #(() implies every ' i ( path contains a vertex ) such that #()) *# (')% A &-ranking is minimal if the reduction of any label greater than 1 violates the described ranking property. The a-rank number of denoted +!(!) equals the largest & such that ! has a minimal &-ranking. We establish new results involving minimal rankings of paths and in particular we determine +!(,) a problem suggested by Laskar and Pillone in 2000. We show +!(, )= blog2 (- +1 )c + j log2 ³ - +1 i ³ 2 blog2 ci1 ´´k