2014/01/12 by Daniel C. McDonald, McDonald, Daniel C.
Computer Science · Mathematics · #05C15 (Secondary) #05C78 (Primary) 05C05 #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #FOS: Mathematics #Optimization and Search Problems #math.CO #msc:05C05 #msc:05C15 #msc:05C78
paper · pdf · doi:10.48550/arxiv.1401.2669
9 pages, 3 figures
arxiv created 2014/01/12 · openalex publication_date 2014/01/12 · arxiv updated 2014/01/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
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. Applications of rankings include VLSI design, parallel computing, and factory scheduling. The on-line ranking problem asks for an algorithm to rank the vertices of G as they are presented one at a time along with all previously ranked vertices and the edges between them (so each vertex is presented as the lone unranked vertex in a partially labeled induced subgraph of G whose final placement in G is not specified). The on-line ranking number of G is the minimum over all such algorithms of the largest label that algorithm can be forced to use. We give bounds on the on-line ranking number of trees in terms of maximum degree, diameter, and number of interior vertices.