Minimal rankings and the a-rank number of a path

Show simple item record

dc.contributor.author Kostyuk, Victor en_US
dc.contributor.author Narayan, Darren en_US
dc.contributor.author Shults, Victoria en_US
dc.date.accessioned 2007-09-13T02:10:16Z en_US
dc.date.available 2007-09-13T02:10:16Z en_US
dc.date.issued 2006-08-28 en_US
dc.identifier.citation Discrete Mathematics 306N16 (2006) 1991-1996 en_US
dc.identifier.issn 0012-365X en_US
dc.identifier.uri http://hdl.handle.net/1850/4711 en_US
dc.description Copyright 2006 Elsevier Science B.V., Amsterdam. All Rights Reserved. en_US
dc.description.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). en_US
dc.description.sponsorship Research travel support provided by JetBlue Airways, Kay & Tony Carlisi, and Timothy Gilbert. Partially partially supported by a RIT COS Dean’s Summer Research Fellowship Grant. en_US
dc.language.iso en_US en_US
dc.publisher Elsevier Science B.V., Amsterdam en_US
dc.relation.ispartofseries vol. 306 en_US
dc.relation.ispartofseries no. 16 en_US
dc.subject Digraph en_US
dc.subject Feedback arc set en_US
dc.subject Linear ordering en_US
dc.subject Ranking en_US
dc.subject Tournament en_US
dc.title Minimal rankings and the a-rank number of a path en_US
dc.type Article en_US
dc.subject.keyword K-ranking en_US
dc.subject.keyword Graph theory en_US
dc.subject.keyword Minimal rankings en_US

Files in this item

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

This item appears in the following Collection(s)

Show simple item record

Search RIT DML


Advanced Search

Browse