Vol. 2, No. 3, 2009

Download this article
Download this article For screen
For printing
Recent Issues

Volume 17
Issue 2, 183–362
Issue 1, 1–182

Volume 16, 5 issues

Volume 15, 5 issues

Volume 14, 5 issues

Volume 13, 5 issues

Volume 12, 8 issues

Volume 11, 5 issues

Volume 10, 5 issues

Volume 9, 5 issues

Volume 8, 5 issues

Volume 7, 6 issues

Volume 6, 4 issues

Volume 5, 4 issues

Volume 4, 4 issues

Volume 3, 4 issues

Volume 2, 5 issues

Volume 1, 2 issues

The Journal
About the journal
Ethics and policies
Peer-review process
Submission guidelines
Submission form
Editorial board
Editors' interests
ISSN (electronic): 1944-4184
ISSN (print): 1944-4176
Author index
To appear
Other MSP journals
Maximum minimal rankings of oriented trees

Sarah Novotny, Juan Ortiz and Darren Narayan

Vol. 2 (2009), No. 3, 289–295

Given a graph G, a k-ranking is a labeling of the vertices using k labels so that every path between two vertices with the same label contains a vertex with a larger label. A k-ranking f is minimal if for all v V (G) we have f(v) g(v) for all rankings g. We explore this problem for directed graphs. Here every directed path between two vertices with the same label contains a vertex with a larger label. The rank number of a digraph D is the smallest k such that D has a minimal k-ranking. The arank number of a digraph is the largest k such that D has a minimal k-ranking. We present new results involving rank numbers and arank numbers of directed graphs. In 1999, Kratochvíl and Tuza showed that the rank number of an oriented of a tree is bounded by one greater than the rank number of its longest directed path. We show that the arank analog does not hold. In fact we will show that the arank number of an oriented tree can be made arbitrarily large where the largest directed path has only three vertices.

$k$-ranking, ordered coloring, oriented trees
Mathematical Subject Classification 2000
Primary: 05C15, 05C20
Received: 18 August 2008
Revised: 29 April 2009
Accepted: 3 June 2009
Published: 3 October 2009

Communicated by Vadim Ponomarenko
Sarah Novotny
Department of Mathematics
The Johns Hopkins University
Baltimore, MD 21218
United States
Juan Ortiz
Department of Mathematics
Lehigh University
Bethlehem, PA 18015
United States
Darren Narayan
Rochester Institute of Technology
School of Mathematical Sciences
85 Lomb Memorial Drive
Rochester, NY 14623-5604
United States