|
|||||
 |
|
|
|
|
|
Maximum minimal
rankings of oriented trees
Sarah Novotny, Juan Ortiz and Darren Narayan
Vol. 2 (2009), No. 3, 289–295
|
Abstract |
|
Given a graph , a -ranking is a labeling of the vertices using labels so that every path between two vertices with the same label contains a vertex with a larger label. A -ranking is minimal if for all we have for all rankings . 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 is the smallest such that has a minimal -ranking. The arank number of a digraph is the largest such that has a minimal -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. |
Keywords
$k$-ranking, ordered coloring, oriented trees
|
Mathematical Subject Classification 2000
Primary: 05C15, 05C20
|
Milestones
Received: 18 August 2008
Revised: 29 April 2009
Accepted: 3 June 2009
Published: 3 October 2009
Communicated by Vadim Ponomarenko
|
Authors |
| 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 |
|
| http://people.rit.edu/~dansma/ | |
|
