T-colorings and T-edge spans of graphs

Abstract

Suppose G is a graph and T is a set of non-negative integers that contains 0. A T-coloring of G is an assignment of a non-negative integer f(x) to each vertex x of G such that f(x) - f(y) is not an element of T whenever xy is an element of E(G). The edge span of a T-coloring f is the maximum value of f(x) - f(y) over all edges xy, and the T-edge span of a graph G is the minimum value of the edge span of a T-coloring of G. This paper studies the T-edge span of the dth power C-n(d) of the n-cycle C-n for T = {0, 1, 2, ..., k - 1}. In particular, we find the exact value of the T-edge span of C-n(d) for n = 0 or 1 (mod d + 1), and lower and upper bounds for other cases.