Vol. 2, No. 3, 2009

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

Volume 11
Issue 2, 181–359
Issue 1, 1–179

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
Subscriptions
Editorial Board
Editors’ Addresses
Editors’ Interests
Scientific Advantages
Submission Guidelines
Submission Form
Ethics Statement
Editorial Login
Author Index
Coming Soon
Contacts
 
ISSN: 1944-4184 (e-only)
ISSN: 1944-4176 (print)
Maximum minimal rankings of oriented trees

Sarah Novotny, Juan Ortiz and Darren Narayan

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

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.

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/