Max-optimal and sum-optimal labelings of graphs

Given a graph G  , a function f:V(G)→{1,2,…,k}f:V(G)→{1,2,…,k} is a k-ranking of G   if f(u)=f(v)f(u)=f(v) implies that every u−vu−v path contains a vertex w   such that f(w)>f(u)f(w)>f(u). A k-ranking is minimal if the reduction of any label greater than 1 violates the described ranking property.We consider two norms for minimal rankings. The max-optimal   norm ‖f(G)‖∞‖f(G)‖∞ is the smallest k for which G has a minimal k  -ranking. This value is also referred to as the rank number χr(G)χr(G). In this paper we introduce the sum-optimal   norm ‖f(G)‖1‖f(G)‖1 which is the minimum sum of all labels over all minimal rankings. We investigate similarities and differences between the two norms. In particular we show rankings for paths and cycles that are sum-optimal are also max-optimal.

► We introduce the L_1 norm as a measure of rankings.
► We compare this norm versus measuring the largest label in a ranking.
► For paths and cycles, minimizing the sum over all labels in a ranking leads to a ranking where the largest label is minimized.
► We investigate divergence between the two norms for other families of graphs.