% Template for Electronic Journal of Graph Theory and Applications % This file must be in the same folder as EJGTAart.sty and EJGTAhead.jpg \documentclass[12pt]{elsarticle} \usepackage[left=1in,right=1in, top=1.2in,bottom=1.2in]{geometry} \usepackage{EJGTAart} \usepackage{times} \usepackage{amssymb,amsthm,latexsym,amsmath,epsfig,pgf} % Set the volume if you know. \volume{{\bf x} (x)} % Set the starting page \firstpage{1} % Title (or short title) and author name for the header \runauth{ Total Vertex Irregularity Strength of Trees with Maximum Degree Five \hspace{2ex} $\arrowvert$\hspace{2ex} Susilawati et al.} % Put new theorem or any other settings for your document here \newtheorem{theorem}{Theorem}[section] \newtheorem*{theorem A}{Theorem A} \newtheorem*{theorem B}{N\"olker's Theorem} \newtheorem{open}[theorem]{Open Problem} \newtheorem{lemma}{Lemma}[section] \newtheorem{proposition}{Proposition}[section] \newtheorem{corollary}{Corollary}[section] \newtheorem{problem}{Problem} \newtheorem*{question}{Question} \newtheorem {conjecture}{Conjecture} \theoremstyle{remark} \newtheorem{remark}{Remark}[section] \theoremstyle{remark} \newtheorem{remarks}{Remarks} \begin{document} \begin{frontmatter} % Write your paper title here \papertitle{Total Vertex Irregularity Strength of Trees with Maximum Degree Five} %% use optional labels to link authors explicitly to addresses. The label may be more than one, use comma to separate %\author[label1,label]{Susilawati${}^1$} \author[]{Susilawati$^1$} \author[]{Edy Tri Baskoro$^2$} \author[]{Rinovia Simanjuntak$^3$} \address{\small $^{1,2,3}$Combinatorial Mathematics Research Group, Faculty of Mathematics and Natural Sciences,\\ Institut Teknologi Bandung, Jalan Ganesa 10 Bandung, Indonesia \vspace*{2.5ex} {\normalfont susilawati$\_$nurdin@math.itb.ac.id, ebaskoro@math.itb.ac.id, rino@math.itb.ac.id} } \begin{abstract} Let $G$ be a connected graph with vertex-set $V(G)$ and edge-set $E(G)$. A total labeling $\phi : V(G) \cup E(G) \rightarrow \{1,2,\dots,k\}$ is called a \textit{vertex irregular total $k-$labeling} of $G$ if every two distinct vertices $x$ and $y$ in $V(G)$ satisfies $wt(x) \neq wt(y),$ where $wt(x) = \phi(x) + \sum\sb{xz \in E(G)} \phi(xz).$ The \textit{total vertex irregularity strength} of $G,$ denoted by $tvs(G),$ is the minimum $k$ for which $G$ has a vertex irregular total $k-$labeling. In 2010, Nurdin, Baskoro, Salman and Gaos conjectured that the total vertex irregularity strength of any tree $T$ is only determined by the number of vertices of degrees 1, 2 and 3. Precisely, they conjectured that $tvs(T)= \max \big \{t_{1}, t_{2}, t_{3} \big \},$ where $t_{i} = \lceil (1+ \sum \sb {j=1}^{i} n_{i})/(i+1)\rceil$ and $n_{i}$ is the number of vertices of degree $i \in [1,3].$ In this paper, we determine the total vertex irregularity strength of trees with maximum degree five. We prove that in any tree $T$ with maximum degree five, there is an $i \in \{1,2,3\}$ such that $t_{i} \geq \max \{t_{4},t_5\}.$ As a consequence, $tvs$ of such a tree is at least $\max\{t_{1}, t_{2}, t_{3}\}.$ We also give necessary and sufficient conditions for all trees $T$ with maximum degree five and $tvs(T)= t_{1}, t_{2}$ or $t_{3}.$ \let\thefootnote\relax\footnotetext{Received: xx xxxxx 20xx,\quad Accepted: xx xxxxx 20xx.\\[3ex] } \end{abstract} \begin{keyword} % Separate keyword by \sep Irregularity Strength \sep Total Vertex Irregularity Strength \sep Tree % Write the classification number Mathematics Subject Classification : 05C78, 05C05 \end{keyword} \end{frontmatter} %% Main text \section{INTRODUCTION} In \cite{ChartrandJacob}, Chartrand \textit{et.al.} proposed the following problem: assign positive integer labels to the edges of a simple connected graph of order at least 3 in such a way that the graph becomes irregular, i.e., the weights (label sums) at each vertex are distinct. The minimum value of the largest label over all such irregular assignments is well known as the \textit{irregularity strength} of the graph. Motivated by this problem, a survey paper of Gallian \cite{Gallian} and a book of Wallis \cite{Wallis}, Baca \textit{et.al} \cite{Baca01} introduced the total vertex irregularity strength of a graph as follows. Let $G(V,E)$ be a simple graph. For a labeling $\phi : V(G) \cup E(G) \rightarrow \{1,2,3,\dots,k\}$ the weight of a vertex $x$ is defined as $wt(x)= \phi (x) + \sum \sb{xy \in E} \phi(xy).$ $\phi$ is called a vertex irregular total $k-$labeling if for every pair of distinct vertices $x$ and $y$ $wt(x) \neq wt(y)$. The minimum $k$ for which the graph $G$ has a vertex irregular total $k-$labeling is called the \textit{total vertex irregularity strength} of $G$ and is denoted by $tvs(G)$. In the same paper, they proved that $tvs(C_{n}) = \lceil \frac{n+2}{3} \rceil, n \geq 3;~tvs(K_{n}) = 2;~tvs(K_{1},n) = \lceil \frac{n+1}{2}\rceil$; $tvs(C_{n} \times P_{2}) = \lceil \frac{2n+3}{4}\rceil.$ If $T$ is a tree with $m$ pendant vertices and no vertex of degree 2, they proved that $\lceil \frac{m+1}{2} \rceil \leq tvs(T) \leq m$. They also proved that if $G$ is a $(p,q)$ graph with minimum degree $\delta$ and maximum degree $\Delta,$ then $\lceil \frac{p + \delta}{\Delta+1}\rceil \leq tvs(G) \leq p + \Delta -2\delta+1.$ In 2010, Nurdin, Baskoro, Salman and Gaos \cite{Nurdin2} determined the total vertex irregularity strength of trees containing vertices of degree 2, namely a subdivision of a star and a subdivision of a particullar caterpillar. They also improved some of the bounds given in \cite{Baca01} and showed that $tvs$ of tree with $n_{1}$ pendant vertices and no vertex of degree 2 is $\lceil \frac{n_{1}+1}{2}\rceil.$ In the same paper, they also determined the total vertex irregularity strength of trees without vertices of degree two and three. They also conjectured that the total vertex irregularity strength of any tree is only determined by the number of its vertices of degree 1,2, and 3. Precisely, they conjectured that $tvs(T) = max \{t_{1}, t_{2}, t_{3}\}$, where $t_{i} = \lceil (1+\sum\sb{j=1}\sp{i}n_{i}) (i+1)\rceil$ and $n_{i}$ is the number of vertices of degree $i \in [1,3]$, is true. Many paper studied about total vertex irregularity strength of graph, see \cite{Ali, Ali2, Siddiqui, Marcin, Bohman,Diari, Slamin}. Recently, Susilawati, Baskoro and Simanjuntak \cite{Susilawati1} determined total vertex irregularity strength for subdivision of several classes of trees, which include subdivision of caterpillar, subdivision of fire cracker, and subdivision of amalgamation of stars. In other paper \cite{Susilawati2}, we gave exact value for total vertex irregularity strength of trees with maximum degree four. \section{Main Results} We will often use the well-known fact that in every tree $T$ with maximum degree $\Delta \geq 1$ the numbers $n_{i}(T)$ of vertices degree $i$ satisfy the equation $n_{1}= 2 + \sum \sb {i \geq 3}(i-2)n_{i},$ \cite{Nora}. \begin{theorem} \cite{Nurdin2} \label{H1} Let $T$ be a tree with maximum degree $\Delta.$ Let $n_{i}$ be the number of vertices of degree $i,$ then $tvs(T) \geq max \bigg \{\big \lceil \frac{1+n_{1}}{2} \big \rceil, \big \lceil \frac{1+n_{1}+n_{2}}{3} \big \rceil,\dots, \big \lceil \frac{1+n_{1}+n_{2}+ \dots+ n_{\Delta}}{\Delta + 1} \big \rceil \bigg\},~\textit{for}~i=1,2,3\dots,\Delta.$ \end{theorem} From now on, we will only consider trees with maximum degree five. Let $n_{i}$ be the number of vertices of degree $i$. For $1 \leq i \leq 5$, we define $t_{i} =\lceil (1 + \sum \sb {j=1} \sp {i} n_{i})/(i+1)\rceil$. By substituting $n_{1}= 2 + \sum\limits_{i \geq 3}(i-2)n_{i}$ into $t_{i}$, then we have $t_{1} = \big \lceil \frac{90+ 30n_{3} + 60n_{4} + 90n_{5}}{60} \big \rceil, t_{2} = \big \lceil \frac{60+ 20n_{2} + 20n_{3} + 40n_{4} + 60n_{5}}{60} \big \rceil, t_{3} = \big \lceil \frac{45+ 15n_{2} + 30n_{3} + 30n_{4} + 45n_{5}}{60} \big \rceil, t_{4} = \big \lceil \frac{36+ 12n_{2} + 24n_{3} + 36n_{4} + 36n_{5}}{60} \big \rceil,$ and $t_{5} = \big \lceil \frac{30 + 10n_{2} + 20n_{3} + 30n_{4} + 40n_{5}}{60} \big \rceil.$ Let $t_{i} = \big \lceil \frac{q_{i}}{60}\big \rceil$ for $i= 1,2,3,4,5$. Thus $q_{1} = 90 + 30n_{3} + 60n_{4} + 90n_{5},~q_{2} = 60 + 20n_{2} + 20n_{3} + 40n_{4} + 60n_{5},~q_{3} = 45 + 15n_{2} + 30n_{3} + 30n_{4} + 45n_{5}$, $q_{4} = 36 + 12n_{2} + 24n_{3} + 36n_{4} + 36n_{5},$ and $q_{5} = 30 + 10n_{2} + 20n_{3} + 30n_{4} + 40n_{5}$. We start with proving that $t_4$ and $t_{5}$ could not be the maximum among all the $t_i$s. \begin{lemma} Let $T$ be a tree with maximum degree five. Then $t_{5} \leq t_{2}, t_{5} \leq t_{3}$ and there exists some $i \in \{1,4\}$ such that $t_{5} \leq t_{i}$. \end{lemma} \begin{proof} Consider $t_{i} = \big \lceil \frac{q_{i}}{60}\big \rceil$ for $i = 1,2,3,4,5$. Then, we have $q_{1}-q_{5}=60 - 10n_{2} + 10n_{3} + 30n_{4} + 50n_{5}, q_{2}-q_{5} = 30 + 10n_{2} + 10n_{4} + 20n_{5}, q_{3} - q_{5} = 15 + 5n_{2} + 10n_{3} + 5n_{5}$, and $q_{4} - q_{5} = 6 + 2n_{2} + 4n_{3} + 6n_{4} - 4n_{5}$. Since $q_{2}-q_{5}$ and $q_{3}-q_{5}$ are positive, then $t_{5} \leq t_{2}$ and $t_{5} \leq t_{3}.$ Now, we need only to show that either $q_{1}-q_{5}$ or $q_{4} - q_{5}$ is non negative. If $q_{1}-q_{5} \geq 0$ then the proof concludes, otherwise $60 - 10n_{2} + 10n_{3} + 30n_{4} + 50 n_{5} < 0$. This implies $n_{2} > 6 + n_{3} + 3n_{4} + 5n_{5}$. Thus $q_{4} - q_{5} = 6 + 2n_{2} + 4n_{3} + 6n_{4} -4n_{5} > 6 + 2(6 + n_{3} + 3n_{4} + 5n_{5}) + 4n_{3} + 6n_{4} - 4n_{5} = 18 + 6n_{3} + 12n_{4} + 6n_{5} > 0.$ \end{proof} \begin{lemma} Let $T$ be a tree with maximum degree five. Then, there exists some $i \in \{1,2\}$ such that $t_{4} \leq t_{i}$. \end{lemma} \begin{proof} Consider $t_{i} = \big \lceil \frac{q_{i}}{60}\big \rceil$ for $i = 1,2,3,4.$ Then, we have $q_{1}-q_{4}=54 - 12n_{2} + 6n_{3} + 24n_{4} + 54n_{5}$ and $q_{2}-q_{4} = 24 + 8n_{2} - 4n_{3} + 4n_{4} + 24n_{5}.$ Thus, we need only to show that either $q_{1}- q_{4}$ or $q_{2} - q_{4}$ is non negative. If $q_{1} - q_{4} \geq 0$ then the proof concludes. Otherwise, $54-12n_{2} + 6n_{3} + 24n_{4} + 54n_{5} < 0$, and so $n_{2} > 9/2 + 1/2 n_{3} + 2n_{4} + 9/2 n_{5}$. Furthermore, $q_{2} - q_{4} = 24 + 8n_{2} - 4n_{3} + 4n_{4} + 24n_{5} > 24 + 8 (9/2 + 1/2 n_{3} + 2n_{4} + 9/2 n_{5}) - 4n_{3} + 4n_{4} + 24n_{5} = 60 + 20n_{4} + 60n_{5} > 0$. \end{proof} \noindent From two above lemmas, we can conclude that one of $\{t_{1}, t_{2} , t_{3}\}$ is $\max \{t_{1}, t_{2}, t_{3}, t_{4}, t_{5}\}.$ The following three lemmas shall consider the necessary and sufficient conditions in order for a particular $t_i$ to be maximum among $t_{1},t_{2}$, or $t_{3}.$ \begin{lemma}\label{H4} Let $T$ be a tree with maximum degree five. $\max \{t_{1}, t_{2}, t_{3}\} = t_{1}$ if and only if $(2n_{3}-2n_{4}-3n_{5}-3 \leq n_{2} \leq 3/2 + 1/2n_{3} + n_{4} + 3/2n_{5})$ or $(1/2n_{2}-3/2n_{5}-3/2 \leq n_{4} < n_{3} - 1/2n_{2} - 3/2n_{5} - 3/2)$ \end{lemma} \begin{proof} Consider the following two cases.\\ \noindent \textbf{Case 1.} $t_{2} \geq t_{3}.$ Consider $t_{i} = \big \lceil \frac{q_{i}}{60}\big \rceil$ for $i = 1,2,3$. Since $q_{1} = 90 + 30n_{3} + 60n_{4} + 90n_{5}, q_{2} = 60 + 20n_{2} + 20n_{3} + 40n_{4} + 60n_{5}, q_{3} = 45 + 15n_{2} + 30n_{3} + 30n_{4} + 45n_{5}$, and $t_{2}-t_{3} \geq 0$, then $n_{2} \geq 2n_{3} - 2n_{4} - 3n_{5}-3$. Since $\max \{t_{1}, t_{2}, t_{3}\} = t_{1}$, then it implies $t_{1} \geq t_{2}$, that is $90+30n_{3}+60n_{4}+90n_{5} \geq 60+20n_{2}+20n_{3}+40n_{4}+60n_{5}$. This yields $n_{2} \leq 3/2 + 1/2 n_{3} + n_{4} + 3/2 n_{5}$. Then, we have $2n_{3}-2n_{4}-3n_{5}-3 \leq n_{2} \leq 3/2 + 1/2n_{3} + n_{4} + 3/2n_{5}$.\\ \noindent \textbf{Case 2.} $t_{2} < t_{3}.$ Consider $t_{i} = \big \lceil \frac{q_{i}}{60}\big \rceil$ for $i = 1,2,3$. $q_{1} = 90 + 30n_{3} + 60n_{4} + 90n_{5}, q_{2} = 60 + 20n_{2} + 20n_{3} + 40n_{4} + 60n_{5}, q_{3} = 45 + 15n_{2} + 30n_{3} + 30n_{4} + 45n_{5},$ and $t_{3} - t_{2} > 0$, then $n_{3} > 3/2 + 1/2 n_{2} + n_{4} + 3/2 n_{5}$. Since $\max \{t_{1}, t_{2}, t_{3}\}=t_{1}$, then it implies $t_{1} \geq t_{3}$, that is $90+30n_{3}+ 60n_{4}+90n_{5} \geq 45 + 15n_{2}+ 30n_{3} + 30n_{4} + 45n_{5}$. This yields $n_{2} \leq 3 + 2n_{4} + 3n_{5}$. Then, we have $1/2n_{2}-3/2n_{5}-3/2 \leq n_{4} < n_{3} - 1/2n_{2} - 3/2n_{5} - 3/2.$\\ \noindent Then, if $\max \{t_{1}, t_{2}, t_{3}\}=t_{1}$ we have $2n_{3}-2n_{4}-3n_{5}-3 \leq n_{2} \leq 3/2 + 1/2n_{3} + n_{4} + 3/2n_{5}$ or $1/2n_{2}-3/2n_{5}-3/2 \leq n_{4} < n_{3} - 1/2n_{2} - 3/2n_{5} - 3/2.$\\ Conversely, by substituting the conditions $2n_{3}-2n_{4}-3n_{5}-3 \leq n_{2} \leq 3/2 + 1/2n_{3} + n_{4} + 3/2n_{5}$ or $1/2n_{2}-3/2n_{5}-3/2 \leq n_{4} < n_{3} - 1/2n_{2} - 3/2n_{5} - 3/2$ into $t_{i} = \lceil (1+ \sum \sb {j=1}^{i} n_{i})/(i+1)\rceil$ where $i \in \{1,2,3\}$ we could obtain $\max \{t_{1},t_{2},t_{3}\}=t_{1}$. \end{proof} \begin{lemma} \label{H5} Let $T$ be a tree with maximum degree five. $\max\{t_{1}, t_{2}, t_{3}\} = t_{2}$ if and only if $(3/2 + 1/2n_{3} + n_{4} + 3/2n_{5} \leq n_{2} \leq 3 + 2n_{4} + 3n_{5})$ or $(n_{3}-1/2n_{2}-3/2n_{5}-3/2 \leq n_{4} < 1/2n_{2} - 3/2n_{5} - 3/2)$. \end{lemma} \begin{proof} Consider the following two cases.\\ \noindent \textbf{Case 1}. $t_{1} \geq t_{3}$ Consider $t_{i} = \big \lceil \frac{q_{i}}{60}\big \rceil$ for $i = 1,2,3$. Since $q_{1} = 90 + 30n_{3} + 60n_{4} + 90n_{5}, q_{2} = 60 + 20n_{2} + 20n_{3} + 40n_{4} + 60n_{5}, q_{3} = 45 + 15n_{2} + 30n_{3} + 30n_{4} + 45n_{5},$ and $t_{1} - t_{3} \geq 0$ then $n_{2} \leq 3+2n_{4} + 3n_{5}$. Since $\max\{t_{1}, t_{2}, t_{3}\} = t_{2}$, then it implies $t_{2} \geq t_{1}$, that is $60 + 20n_{2} + 20n_{3} + 40n_{4} + 60n_{5} \geq 90 + 30n_{3} + 60n_{4} + 90n_{5}$. This yields $n_{2} \geq 3/2 + 1/2 n_{3} + n_{4} + 3/2 n_{5}$. Then, we have $3/2 + 1/2n_{3} + n_{4} + 3/2n_{5} \leq n_{2} \leq 3 + 2n_{4} + 3n_{5}$.\\ \noindent \textbf{Case 2}. $t_{1} < t_{3}$ Consider $t_{i} = \big \lceil \frac{q_{i}}{60}\big \rceil$ for $i = 1,2,3$. Since $q_{1} = 90 + 30n_{3} + 60n_{4} + 90n_{5}, q_{2} = 60 + 20n_{2} + 20n_{3} + 40n_{4} + 60n_{5}, q_{3} = 45 + 15n_{2} + 30n_{3} + 30n_{4} + 45n_{5},$ and $t_{3} - t_{1} > 0$ then $n_{2} > 3 + 2n_{4} + 3n_{5}$. Since $\max\{t_{1}, t_{2}, t_{3}\} = t_{2}$, then it implies $t_{2} \geq t_{3}$, that is $60 + 20n_{2} + 20n_{3} + 40n_{4} + 60n_{5} \geq 45 + 15n_{2} + 30n_{3} + 30n_{4} + 45n_{5}$. This yields $n_{3} \leq 3/2 + 1/2 n_{2} + n_{4} + 3/2 n_{5}$. Then, we have $n_{3}-1/2n_{2}-3/2n_{5}-3/2 \leq n_{4} < 1/2n_{2}-3/2n_{5}-3/2.$\\ \noindent Then, if $\max\{t_{1}, t_{2}, t_{3}\} = t_{2}$ we have $3/2 + 1/2n_{3} + n_{4} + 3/2n_{5} \leq n_{2} \leq 3 + 2n_{4} + 3n_{5}$ or $n_{3}-1/2n_{2}-3/2n_{5}-3/2 \leq n_{4} < 1/2n_{2}-3/2n_{5}-3/2.$\\ Conversely, by substituting the conditions $3/2 + 1/2n_{3} + n_{4} + 3/2n_{5} \leq n_{2} \leq 3 + 2n_{4} + 3n_{5}$ or $n_{3}-1/2n_{2}-3/2n_{5}-3/2 \leq n_{4} < 1/2n_{2}-3/2n_{5}-3/2$ into $t_{i} = \lceil (1+ \sum \sb {j=1}^{i} n_{i})/(i+1)\rceil$ where $i \in \{1,2,3\}$ we could obtain $\max \{t_{1},t_{2},t_{3}\}=t_{2}$. \end{proof} \begin{lemma} \label{H6} Let $T$ be a tree with maximum degree five. $\max \{t_{1}, t_{2}, t_{3}\} = t_{3}$ if and only if $(3 + 2n_{4} + 3n_{5} \leq n_{2} \leq 3/2 + 1/2n_{3} + n_{4} + 3/2n_{5})$ or $(3/2 + 1/2n_{3} + n_{4} + 3/2n_{5} < n_{2} \leq 2n_{3} - 2n_{4} - 3n_{5} -3)$. \end{lemma} \begin{proof} Consider the following two cases.\\ \noindent \textbf{Case 1}. $t_{1} \geq t_{2}$. Consider $t_{i} = \big \lceil \frac{q_{i}}{60}\big \rceil$ for $i = 1,2,3$. Since $q_{1} = 90 + 30n_{3} + 60n_{4} + 90n_{5}, q_{2} = 60 + 20n_{2} + 20n_{3} + 40n_{4} + 60n_{5}, q_{3} = 45 + 15n_{2} + 30n_{3} + 30n_{4} + 45n_{5},$ and $t_{1} - t_{2} \geq 0$ then $n_{2} \leq 3/2 + 1/2 n_{3} + n_{4} + 3/2 n_{5}.$ Since $\max \{t_{1}, t_{2}, t_{3}\} = t_{3},$ then it implies $t_{3} \geq t_{1},$ that is $45 + 15n_{2} + 30n_{3} + 30n_{4} + 45n_{5} \geq 90 + 30n_{3} + 60n_{4} + 90n_{5}.$ This yields $n_{2} \geq 3 + 2n_{4} +3n_{5}.$ Then, we have $3 + 2n_{4} + 3n_{5} \leq n_{2} \leq 3/2 + 1/2 n_{3} + n_{4} + 3/2n_{5}$.\\ \noindent \textbf{Case 2}. $t_{1} < t_{2}$. Consider $t_{i} = \big \lceil \frac{q_{i}}{60}\big \rceil$ for $i = 1,2,3$. Since $q_{1} = 90 + 30n_{3} + 60n_{4} + 90n_{5}, q_{2} = 60 + 20n_{2} + 20n_{3} + 40n_{4} + 60n_{5}, q_{3} = 45 + 15n_{2} + 30n_{3} + 30n_{4} + 45n_{5},$ and $t_{2} - t_{1} > 0$ then $n_{2} > 3/2 + 1/2 n_{3} + n_{4} +3/2 n_{5}.$ Since $\max \{t_{1}, t_{2}, t_{3}\}= t_{3},$ then it implies $t_{3} \geq t_{2}$ that is $45 + 15n_{2} + 30n_{3} + 30n_{4} + 45n_{5} \geq 60 + 20n_{2} + 20n_{3} + 40n_{4} + 60n_{5}.$ This yields $n_{2} \leq 2n_{3} - 2n_{4} - 3n_{5} -3$. Then, we have $3/2 + 1/2n_{3} + n_{4} + 3/2n_{5} < n_{2} \leq 2n_{3} - 2n_{4} - 3n_{5}-3.$\\ \noindent Then, if $\max \{t_{1}, t_{2}, t_{3}\} = t_{3}$ we have $3 + 2n_{4} + 3n_{5} \leq n_{2} \leq 3/2+1/2n_{3}+n_{4}+3/2n_{5}$ or $3/2 + 1/2n_{3} + n_{4} + 3/2n_{5} < n_{2} \leq 2n_{3} - 2n_{4} - 3n_{5}-3.$\\ Conversely, by substituting $3 + 2n_{4} + 3n_{5} \leq n_{2} \leq 3/2 + 1/2n_{3} + n_{4} + 3/2n_{5}$ or $3/2 + 1/2n_{3} + n_{4} + 3/2n_{5} < n_{2} \leq 2n_{3} - 2n_{4} - 3n_{5}-3$ into $t_{i} = \lceil (1+ \sum \sb {j=1}^{i} n_{i})/(i+1)\rceil$ where $i \in \{1,2,3\}.$ Then, we could obtain $\max \{t_{1}, t_{2}, t_{3}\} = t_{3}.$ \end{proof} Next, in Theorem \ref{teorema1}, we characterize trees with maximum degree five such that $tvs(T)= t_{1}.$ In Theorem \ref{teorema2} and \ref{teorema3}, we show similar characterization for $tvs(T) = t_{2}$ and $tvs(T)=t_{3}$, respectively. We call $v$ an \textit{exterior vertex} if there exist a pendant vertex which is adjacent to $v$. A vertex $v$ which is neither an exterior vertex nor a pendant vertex is called an interior vertex. \begin{theorem} \label{teorema1} Let $T$ be a tree with maximum degree five. $tvs(T)= t_{1}$ if and only if $(2n_{3}-2n_{4}-3n_{5}-3 \leq n_{2} \leq 3/2 + 1/2n_{3} + n_{4} + 3/2n_{5})$ or $(1/2n_{2} - 3/2 n_{5} - 3/2 \leq n_{4} < n_{3} - 1/2n_{2} - 3/2n_{5} - 3/2)$. \end{theorem} \begin{proof} \noindent According to Lemma \ref{H4} and Theorem \ref{H1}, we have $tvs(T) \geq t_{1}$ if and only if $(2n_{3}-2n_{4}-3n_{5}-3 \leq n_{2} \leq 3/2 + 1/2n_{3} + n_{4} + 3/2n_{5})$ or $(1/2n_{2} - 3/2 n_{5} - 3/2 \leq n_{4} < n_{3} - 1/2n_{2} - 3/2n_{5} - 3/2).$ We need to show that $tvs(T) \leq t_{1}.$ Define a total labeling $\phi : V(T) \cup E(T) \rightarrow \{1,2,\dots,t_{1}\}$ in $T$ by using the following algorithm.\\ \noindent \textbf{\underline{Labeling Algorithm 1}}\\ \noindent Label all edges $e \in E(T)$ by the following steps. \begin{itemize} \item [(a).] Let $W = \{w_{1}, w_{2}, \dots, w_{k}\}$ be the set of exterior vertices, where $d(w_{i}) \geq d(w_{i+1})$ and $|E(w_{i})| \geq |E(w_{i+1})|$ where $E(w_{i})$ is the set of pendant edges incident to $w_{i}$.\\ Let $E_{1}= \bigcup \sb {i=1} E(w_{i})$ be an ordered set of all pendant edges in $T$. \item [(b).] Label the first $t_{1}$ pendant edges $e \in E_{1}$ with $\{1,2,3, \dots t_{1}\},$ respectively. \item [(c).] For all the remaining edges $e \in E(T)-E_{1}$, we define $\phi(e) = t_{1}$. \end{itemize} \noindent Label all vertices $v \in V(T)$ by the following steps. \begin{itemize} \item[(a).] Let $V_{1} = \{w_{ij} | i=1,2,3,\dots,k$ \mbox{and} $j=1,2,3,\dots,j_{i} \}$ be an ordered set of pendant vertices adjacent to $w_{i}$, where $j_{i}$ is the number of pendant vertices adjacent to $w_{i}$. \item[(b).] Label the first $t_{1}$ pendant vertices in $V_{1}$ with $1$. \item[(c).] Label $(n_{1}-t_{1})$ remaining pendant vertices with $2,3,\dots, n_{1}-t_{1}+1$. \item[(e).] Define $s(y) = \sum\limits_{yz \in E(T)}\phi(yz),$ as a temporary weight of a vertex $y$ where $y \in V/V_{1}$. \item[(f).] Denote all vertices in $V/V_{1}$ by $y_{1}, y_{2}, y_{3}, \dots, y_{N}$, where $N=n_{2}+n_{3}+n_{4}+\dots+n_{\Delta}$, such that $s(y_{1}) \leq s(y_2) \leq s(y_{3}) \leq \dots \leq s(y_{N})$. \item[(g).] We define $\phi(y_{i})$ recursively as follows.$$\phi(y_{1})=n_{1}+2-s(y_{1}),$$ which implies $wt(y_{1})=\phi(y_{1})+s(y_{1})$. For $2 \leq i \leq N,$ we define $$\phi(y_{i})= \mbox{max} \{1,wt(y_{i-1})+1-s(y_{i})\}.$$ \end{itemize} We observe that $\phi$ is a labeling from $V(T) \cup E(T)$ into $\{1,2,3,\dots,t_{1}\}$ where the weights of $n_{1}$ pendant vertices are $\{2,3,4,\dots,n_{1}+1\}$ and the weights of all remaining vertices are $n_{1}+2 = wt(y_{1}) < wt(y_{2}) < wt(y_{3}) < \dots < wt(y_{N}).$ Therefore, $tvs(T) \leq t_{1}$. \end{proof} \begin{theorem} \label{teorema2} Let $T$ be a tree with maximum degree five. $tvs(T)=t_{2}$ if and only if $(3/2+1/2n_{3}+n_{4}+3/2n_{5} \leq n_{2} \leq 3+ 2n_{4} +3n_{5})$ or $(n_{3} - 1/2n_{2} - 3/2n_{5}-3/2 \leq n_{4} < 1/2n_{2}-3/2n_{5}-3/2).$ \end{theorem} \begin{proof} \noindent According to Lemma \ref{H5} and Theorem \ref{H1}, we have $tvs(T) \geq t_{2}$ if and only if $(3/2+1/2n_{3}+n_{4}+3/2n_{5} \leq n_{2} \leq 3+ 2n_{4} +3n_{5})$ or $(n_{3} - 1/2n_{2} - 3/2n_{5}-3/2 \leq n_{4} < 1/2n_{2}-3/2n_{5}-3/2).$ We will show that $tvs(T) \leq t_{2}.$ We define a total labeling $\phi : V(T) \cup E(T) \rightarrow \{1,2,\dots,t_{2}\}$ in $T$ by using Labeling Algorithm 2 where $i=2$ as follow.\\ \noindent \textbf{\underline{Labeling Algorithm 2}}\\ \noindent Label all edges $e \in E(T)$ by the following steps. \begin{enumerate} \item[(a).] Let $W = \{w_{1},w_{2},w_{3},\dots,w_{k}\}$ be the set of exterior vertices, where $d(w_{i}) \geq d(w_{i}+1), \forall i$ and $|E(w_{i})| \geq |E(w_{i+1})|$ where $E(w_{i})$ is the set of pendant edges incident to $w_{i}.$ Let $E_{1}= \bigcup \sb {i=1} E(w_{i})$ be an ordered set of all pendant edges in $T.$ \item[(b).] Label the first $t_{i}$ pendant edges in $E_{1}$ with $\{1,2,3,\dots,t_{i}\},$ respectively. \item[(c).] Label $(n_{1}-t_{i})$ remaining pendant edges $e \in E_{1}$ with $t_{i}.$ \item[(d).] Let $E_{2}$ be the ordered set of edges not in $E_{1}$ where at least one of the end vertices of degree two. Denote by $e_{i}$ where $i = 1, 2,\dots, n_{2},$ the edges in $E_{2}$ and we define $\phi(e_{i}) = \lceil \frac{1+n_{1}+i}{3}\rceil$. \item[(e).] Label all remaining edges $e \in E(T)-E_{1}(T)-E_{2}(T)$ with $t_{i}$. \end{enumerate} \noindent Label all vertices $v \in V(T)$ by the following steps. \begin{enumerate} \item[(a).] Let $V_{1}=\{w_{ij} | i=1,2,3,\dots,k ~ \mbox{and}~ j=1 ,2,3,\dots,j_{i}\}$ be an ordered set of pendant vertices adjacent to $w_{i},$ where $j_{i}$ is the number of pendant vertices adjacent to $w_{i}.$ \item[(b).] Label the first $t_{i}$ pendant vertices in $V_{1}$ with 1. \item[(c).] Label the $(n_{1}-t_{i})$ remaining pendant vertices with $2,3,4, \dots, n_{1}-t_{i}+1.$ \item[(d).] Denote all vertices in $V / V_{1}$ by $y_{1},y_{2},y_{3}, \dots, y_{N},$ where $N=n_{2} + n_{3} + n_{4} + \dots+n_{\Delta},$ such that $s(y_{1}) \leq s(y_{2}) \leq s(y_{3}) \leq \dots \leq s(y_{N}),$ with $s(y) = \sum\limits_{yz \in E(T)}\phi (yz)$, which can be considered as a temporary weight of $y.$ \item[(e).] We define $\phi(y_{i})$ recursively as follows, $\phi(y_{1})= n_{1}+2-s(y_{1}),$ which implies $wt(y_{1}) = \phi(y_{1}) + s(y_{1}).$ For $2 \leq i \leq N,$ $\phi(y_{i}) = \mbox{max} \{1, wt(y_{i-1}) + 1 - s(y_{i})\}.$ \end{enumerate} We conclude that $\phi$ is a labeling from $V(T) \cup E(T)$ into $\{1,2,\dots,t_{2}\}$ and the weights of all pendant vertices form a sequence $1,2,3,4,\dots,n_{1}+1$ and the weight of all remaining vertices are $n_{1}+2 = wt(y_{1}) < wt(y_{2}) < \dots < wt(y_{N}).$ Therefore, $tvs(T) \leq t_{2}.$ \end{proof} \begin{theorem}\label{teorema3} Let $T$ be a tree with maximum degree five. $tvs(T)= t_{3}$ if and only if $(3+2n_{4}+3n_{5} \leq n_{2} \leq 3/2+1/2n_{3} + n_{4} + 3/2n_{5})$ or $(3/2+1/2n_{3}+n_{4}+3/2n_{5} < n_{2} \leq 2n_{3} - 2n_{4} - 3n_{5} - 3).$ \end{theorem} \begin{proof} According to Lemma \ref{H6} and Theorem \ref{H1}, we have $tvs(T) \geq t_{3}$ if and only if $(3+2n_{4}+3n_{5} \leq n_{2} \leq 3/2+1/2n_{3} + n_{4} + 3/2n_{5})$ or $(3/2+1/2n_{3}+n_{4}+3/2n_{5} < n_{2} \leq 2n_{3} - 2n_{4} - 3n_{5} - 3).$ We will show that $tvs(T) \leq t_{3}.$ We define a total labeling $\phi : V(T) \cup E(T) \rightarrow \{1,2,3,\dots,t_{3}\}$ in $T$ by using Labeling Algorithm 2 where $i=3.$ We conclude that $\phi$ is a labeling from $V(T) \cup E(T)$ into $\{1,2,\dots,t_{i}\}$ and the weights of all pendant vertices form a sequence $1,2,3,4,\dots,n_{1}+1$ and the weight of all remaining vertices are $n_{1}+2 = wt(y_{1}) < wt(y_{2}) < \dots < wt(y_{N}).$ Therefore, $tvs(T) \leq t_{3}.$ \end{proof} \section{Conclusion} In these results, we proved that for any tree $T$ of maximum degree five, the total vertex irregularity strength of tree is $\mbox{max} \{t_{1}, t_{2}, t_{3}\}$ which verify the conjecture Nurdin \textit{et.al} (2010). In particular, we give necessary and sufficient conditions for all tree $T$ with maximum degree five such that the total vertex irregularity strength at least $\{t_{1}, t_{2}, t_{3}\}.$ To conclude this paper, we give an open problem below. \begin{open} Find the total vertex irregularity strength of trees with maximum degree at least 6. \end{open} %-------------------------------------------------------------------- \subsection*{Acknowledgment} This research was supported by Research Grant ``Program PMDSU DIKTI'', Indonesia Ministry of Research, Technology and Higher Education. \section*{References} \begin{thebibliography}{99} \bibitem{Ali} A. Ahmad, K.M. Awan, I. Javaid, Slamin, Total Vertex Irregularity Strength of Wheel Related Graphs, {\it Australian Journal of Combinatorics}, \textbf{51} (2011), 147--156. \bibitem{Ali2} A. Ahmad, M. Ba\u{c}a, Y. Bashir, Total Vertex Irregularity Strength of Certain Classes of Unicyclic Graphs, {\it Bull. Math. Soc. Sci. Math. Roumanie}, \textbf{2} (2014), 147-152. \bibitem{Siddiqui} O. Al-Mushayt, A. Arshad, M. K. Siddiqui, Total Vertex Irregularity Strength of Convex Polytope Graphs, {\it Acta Math. Univ. Comenianae}, \textbf{LXXXII} (1) (2013), 29-37. \bibitem{Marcin} M. Anholcer, M. Karo\'{n}ski, F. Pfender, Total Vertex Irregularity Strength of Forest, {\it arXiv preprint arXiv:1103.2087} (2011). \bibitem{Baca01} M. Ba\u{c}a, S. Jendrol', M. Miller, J. Ryan, On Irregular Total Labellings, {\it Discrete Mathematics}, \textbf{307} (2007), 1378-1388. \bibitem{Bohman} T. Bohman, D. Kravitz, On the Irregularity Strength of Trees, {\it Journal of Graph Theory}, \textbf{45} (4) (2004), 241--254. \bibitem{ChartrandJacob} G. Chartrand, M. S. Jacobson, J. Lehel, O. R. Oellermann, S. Ruiz, F. Saba, Irregular Network, {\it Congr Numer}, \textbf{64} (1988), 187-192. \bibitem{Gallian} J. A. Gallian, A Dynamic Survey of Graph Labeling, {\it Electronic J. Combin}, {\bf 17} (2014), $\#$DS6. \bibitem{Nora} N. Hartsfield, G. Ringel, Pearls in Graph Theory, A Comprehensive Introduction, {\it Academic Press, INC.} (1990). \bibitem{Diari} D. Indriati, W. I. E. Wijayanti, K. A. Sugeng, M. Ba\u{c}a, A. Semani\u{c}ov\'{a}-Fe\v{n}ov\u{c}\'{\i}kov\'{a}, The Total Vertex Irregularity Strength of Generalized Helm Graphs and Prism with Outer Pendant Edges, {\it Australian Journal of Combinatorics}. \textbf{65}(1) (2016), 14-26. \bibitem{Nurdin2} Nurdin, E. T. Baskoro, A. N. M. Salman, N. N. Gaos, On Total Vertex Irregularity Strength of Trees, {\it Discrete Mathematics}, \textbf{310} (2010), 3043--3048. \bibitem{Slamin} Slamin, Dafik, W. Winnona, Total Vertex Irregularity Strength of the Disjoint Union of Sun Graphs, {\it International Journal of Combinatorics}, \textbf{2012} (2012), 1--9. \bibitem{Susilawati1} Susilawati, E. T. Baskoro, R. Simanjuntak, Total Vertex Irregularity Labelings for Subdivision of Several Classes of Tree, {\it Procedia Computer Science}, \textbf{74} (2015), 112--117. \bibitem{Susilawati2} Susilawati, E. T. Baskoro, R. Simanjuntak, Total Vertex Irregularity Strength of Tree with Maximum Degree Four, {\it AIP Conference Proceedings}, \textbf{1707} 020022 (2016); doi: 10.1063/1.4940823. \bibitem{Wallis} W. D. Wallis, Magic Graphs, {\it Birkh\"{a}user}, Boston (2001). \end{thebibliography} \end{document} %% %% End of file `ecrc-template.tex'.