On T and ST-coloring of n-Hypercube graph and Kragujevac tree

Abstract

Let G = (V, E) denotes any graph, where V represents the vertex set and E represents the edge set. Then, T-coloring of a graph is an assignment of non-negative numbers to the vertices of a graph such that the difference between the colors assigned to the adjacent vertices does not belong to a predefined set of non-negative integers known as a T set, which must include zero. Ordinary vertex coloring of a graph is also a particular type of T-coloring. In this paper, we consider the T-set of the form T = {0, 1, 2, . . . , k}∪S, where S is any arbitrary set that does not contain any multiple of (k + 1), and is termed as k-initial set. We also consider the T−set of the form T = {0, s, 2s, . . . , ks}∪S, where S is a subset of the set {s+ 1, s+ 2, s+ 3, . . . , , ks}, ks ≥ 1 and is termed as a k-multiple of s set. We study the T-coloring on n-Hypercube graph and Tree graphs for any k-initial set and k-multiple of s set. For measuring the efficiency of the T-coloring, we also analyze two special parameters, firstly the T-span, which is being the maximum of | f(u)−f(w) |over all the vertices u and w and secondly, the edge-span, denoted as espT (G), which is being the maximum of | f(u) − f(w) | over all the edges (u, w) of G. We also study the strong T-coloring (ST-coloring ) of G on Kragujevac tree.