Minimal k-rankings and the a-rank number of a path

Show full item record

Title: Minimal k-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 a-rank number of G, denoted u,(G) equals the largest k such that G has a minimal k-ranking. We establish new results involving minimal rankings of paths and in particular we determine u(Pn), a problem suggested by Laskar and Pillone in 2000. We show u(Pn) = [log2 (n + 1)] + [log2(n + 1 - (2^([log2n]-1))] (Refer to PDF file for exact formulas).
Description: Presentation at the 34th Southeastern International Conference on Combinatorics, Graph Theory, and Computing, Florida Atlantic University, Boca Raton, FL, March 2003.
Record URI: http://hdl.handle.net/1850/4757
Date: 2003-08-17

Files in this item

Files Size Format View
DNarayanArticle08-17-2003.pdf 150.3Kb 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

Browse