2014/01/15 by Daniel C. McDonald, McDonald, Daniel C.
Computer Science · Mathematics · #05C15 #05C38 (Secondary) #05C78 (Primary) 05C05 #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #FOS: Mathematics #Graph Labeling and Dimension Problems #math.CO #msc:05C05 #msc:05C15 #msc:05C38 #msc:05C78
paper · pdf · doi:10.48550/arxiv.1401.3498
16 pages, 3 figures
arxiv created 2014/01/15 · openalex publication_date 2014/01/15 · arxiv updated 2014/01/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A k-ranking of a graph G is a labeling of its vertices from \1,…,k\ such that any nontrivial path whose endpoints have the same label contains a larger label. The least k for which G has a k-ranking is the ranking number of G, also known as tree-depth. The list ranking number of G is the least k such that if each vertex of G is assigned a set of k potential labels, then G can be ranked by labeling each vertex with a label from its assigned list. Rankings model a certain parallel processing problem in manufacturing, while the list ranking version adds scheduling constraints. We compute the list ranking number of paths, cycles, and trees with many more leaves than internal vertices. Some of these results follow from stronger theorems we prove about on-line versions of list ranking, where each vertex starts with an empty list having some fixed capacity, and potential labels are presented one by one, at which time they are added to the lists of certain vertices; the decision of which of these vertices are actually to be ranked with that label must be made immediately.