Greedy rankings and arank numbers |
| |
Authors: | Garth Isaak Darren Narayan |
| |
Affiliation: | a Department of Mathematics, Lehigh University, Bethlehem, PA 18015, United States b Department of Mathematical Sciences, Clemson University, Clemson, SC 29634, United States c School of Mathematical Sciences, Rochester Institute of Technology, Rochester, NY 14623, United States |
| |
Abstract: | A ranking on a graph is an assignment of positive integers to its vertices such that any path between two vertices of the same rank contains a vertex of strictly larger rank. A ranking is locally minimal if reducing the rank of any single vertex produces a non-ranking. A ranking is globally minimal if reducing the ranks of any set of vertices produces a non-ranking. A ranking is greedy if, for some ordering of the vertices, it is the ranking produced by assigning ranks in that order, always selecting the smallest possible rank. We will show that these three notions are equivalent. If a ranking satisfies one property it satisfies all three. As a consequence of this and known results on arank numbers of paths we improve known upper bounds for on-line ranking of paths and cycles. |
| |
Keywords: | Graph algorithms Vertex coloring On-line ranking number Rank number Minimal rankings |
本文献已被 ScienceDirect 等数据库收录! |
|