List rankings and on-line list rankings of graphs

DOI10.1016/J.DAM.2015.12.014MaRDI QIDQ266945zbMATH OpenOpenAlexFDO

Authors Daniel C. McDonald

Publication date 7 April 2016

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1401.3498

zbMATH Keywords

list rankingon-line list rankingranking numbertree-depthvertex ranking

Mathematics Subject Classification ID

Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Abstract: A $k$-ranking of a graph $G$ is a labeling of its vertices from $1,ldots,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.

Recommendations

• On-line rankings of graphs
• Rankings of Graphs
• Rankings of graphs
• A note on on-line ranking number of graphs
• Ranking numbers of graphs
• On graphs associated to sets of rankings
• Rankings of Directed Graphs
• On-line ranking of split graphs
• On order and rank of graphs
• Online ranking for tournament graphs

Cites work

• scientific article; zbMATH DE number 5844196 (Why is no real title available?)
• scientific article; zbMATH DE number 2076918 (Why is no real title available?)
• Characterisations and examples of graph classes with bounded expansion
• Edge ranking and searching in partial orders
• Grad and classes with bounded expansion. I: Decompositions
• Grad and classes with bounded expansion. II: Algorithmic aspects
• Grad and classes with bounded expansion. III: Restricted graph homomorphism dualities
• Greedy rankings and arank numbers
• LIFO-search: a min-max theorem and a searching game for cycle-rank and tree-depth
• Mr. Paint and Mrs. Correct
• On an edge ranking problem of trees and graphs
• On-line ranking number for cycles and paths
• On-line vertex ranking of trees
• Optimal node ranking of trees
• Rankings of Graphs
• Tree-depth, subgraph coloring and homomorphism bounds

Cited in

(2)

• Graph 2-rankings
• On-line vertex ranking of trees

This page was built for publication: List rankings and on-line list rankings of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q266945)