On Total Irregularity Strength of Star Graphs, Double-Stars and Caterpillar

摘要

For a simple graph G = (V,E) with the vertex set V and the edge set E, a totally irregular total k-labeling f: V ∪ E → { 1,2,...,k} is a labeling of vertices and edges of G in such a way that for any two different vertices x and x', their weights wt_f(x) = f(x) + ∑_(xy∈E) f(xy) and wt_f(x') = f(x') + ∑_(x'y'∈E) f(x'y') are distinct, and for any two different edges xy and x'y' their weights f(x) + f(xy) + f(y) and f(x') + f(x'y') + f(y') are also distinct. A total irregularity strength of graph G, denoted by ts(G), is defined as the minimum k for which G has a totally irregular total k-labeling. In this paper, we determine the exact value of the total irregularity strength for star graphs, double stars and caterpillar.