Minimal rankings and the a-rank number of a path

Show full item record

Redirect: RIT Scholars content from RIT Digital Media Library has moved from to RIT Scholar Works, please update your feeds & links!
Title: Minimal rankings and the a-rank number of a path
Author: Kostyuk, Victor; Narayan, Darren; Shults, Victoria
Abstract: Given a graph G, a function f:V(G)→ {1,2,…,k} is a k-ranking of G if f(u)=f(v) implies every u-v path contains a vertex w such that f(w)>f(u). A k-ranking is minimal if the reduction of any label greater than 1 violates the described ranking property. The arank number of a graph, denoted ψr(G), is the largest k such that G has a minimal k-ranking. We present new results involving minimal k-rankings of paths. In particular, we determine ψr(Pn), a problem posed by Laskar and Pillone in 2000 (Refer to PDF file for exact formulas).
Description: Copyright 2006 Elsevier Science B.V., Amsterdam. All Rights Reserved.
Record URI:
Date: 2006-08-28

Files in this item

Files Size Format View
DNarayanArticle08-28-2006.pdf 176.2Kb PDF View/Open

The following license files are associated with this item:

This item appears in the following Collection(s)

Show full item record

Search RIT DML

Advanced Search