A lower bound for on-line ranking number of a path Original Research Article

A k-ranking of a graph G is a mapping image such that any path with endvertices x and y satisfying image and image contains a vertex z with image. The ranking number image of G is the minimum k admitting a k-ranking of G. The on-line ranking number image of G is the corresponding on-line invariant; in that case vertices of G are coming one by one so that a partial ranking has to be chosen by considering only the structure of the subgraph of G induced by the present vertices. It is known that image. In this paper it is proved that image.