ON T AND ST-COLORING OF n-HYPERCUBE GRAPH AND KRAGUJEVAC TREE

ON T AND ST-COLORING OF n-HYPERCUBE GRAPH AND KRAGUJEVAC TREE

R. Moran , N. Bora

[PDF]

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.

Keywords

T-coloring, T-set, n-Hypercube graph, Kragujevac tree.