Total Vertex Irregularity Strength of Forests

Abstract

We investigate a graph parameter called the total vertex irregularity strength ($tvs(G)$), i.e. the minimal $s$ such that there is a labeling $w:E(G)\cup V(G)\to \{1,2,..,s\}$ of the edges and vertices of $G$ giving distinct weighted degrees $w{t}_G(v):=w(v)+{\sum }_{v\in e\in E(G)}w(e)$ for every pair of vertices of $G$. We prove that $tvs(F)=\lceil (n_1+1)/2\rceil$ for every forest $F$ with no vertices of degree 2 and no isolated vertices, where $n_1$ is the number of pendant vertices in $F$. Stronger results for trees were recently proved by Nurdin et al.

The stronger results for trees were recently proved by Nurdin et al. (Nurdin, Baskoro E.T., Salman A.N.M., Gaos N.N., On the Total Vertex Irregularity Strength of Trees, Discrete Mathematics 310 (2010), 3043-3048.). However we decided to publish our paper for two reasons. Firstly, we consider more general case of forests, not only trees. Secondly, we use different proof technique