T-Colorings and T-Edge Spans of Graphs |
| |
Authors: | Shin-Jie Hu Su-Tzu Juan Gerard J Chang |
| |
Institution: | (1) Department of Applied Mathematics, National Chiao Tung University, Hsinchu 30050, Taiwan. e-mail: gjchang@math.nctu.edu.tw, TW |
| |
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)|∉T whenever xy∈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
d
n 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 (mod d+1), and lower and upper bounds for other cases.
Received: May 13, 1996 Revised: December 8, 1997 |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|