TOTAL VERTEX IRREGULARITY STRENGTH OF TREES WITH MAXIMUM DEGREE FOUR - Susilawati
Baca et al. (2007) introduced the concept of total vertex irregularity labeling. A total vertex irregular k-labeling of G is defined as a mapping from the vertex and edge of G to f1;2; : : : ;kg such that each vertex of G has a distinct weight. The weight of a vertex x 2 V is the sum of the label of x and the labels of all edges incident to x. The total vertex irregularity strength of G, denoted by tvs(G), is the smallest positive integer k such that G has a total vertex irregular k-labeling. Some results on tvs(G) have been obtained for several classes of graphs G. For instance, Nurdin, Baskoro, Salman and Gaos determined the total vertex irregularity strength of paths, trees without vertices of degree 2 and 3, quadtrees and banana trees. They conjectured that the total vertex irregularity strength of any tree is only determined by the number of vertices of degree 1, 2, and 3. Precisely, they conjectured this formula: tvs(T) = maksft1; t2; t3g where ti = d(1 + åi j=1 ni)=(i + 1)e and ni is the number of vertices of degree i 2 [1;3]. In this thesis, we verify this conjecture by considering all trees with maximum degree four and subdivision of some trees.