Characterization of trees with total vertex irregularity strength -t_1-
Faisal Susanto (a), Rinovia Simanjuntak (a,b), Edy Tri Baskoro (a,b*)

a) Combinatorial Mathematics Research Group
Faculty of Mathematics and Natural Sciences, Institut Teknologi Bandung
Jalan Ganesa 10 Bandung, 40132, Indonesia
b) Center for Research Collaboration on Graph Theory and Combinatorics, Indonesia
*ebaskoro[at]itb.ac.id

Abstract

For a simple graph -G(V,E)- and a positive integer -k-, a vertex irregular total -k--labeling of -G- is a mapping -\varphi:V\cup E\rightarrow\{1,2,\dots,k\}- such that -wt(x)\ne wt(y)- for any two distinct vertices -x,y\in V-, where -wt(x)=\varphi(x)+\sum_{xz\in E}\varphi(xz)-. The minimum -k- for which -G- has a vertex irregular total labeling is called the total vertex irregularity strength of -G- and it is denoted by -\mathrm{tvs}(G)-. Finding the total vertex irregularity strengths for all trees is a difficult and a challenging problem, see [2,3,4] to mention a few results on that topic. Nurdin, Baskoro, Salman and Gaos [1] conjectured that for every tree -T-, -\mathrm{tvs}(T)=\max\{t_1,t_2,t_3\}-, where -t_i=\lceil(\sum_{j=1}^in_j+1)/(i+1)\rceil- and -n_j- denotes the number of vertices of degree -j- in -T-. In this talk, we characterize all trees having the total vertex irregularity strength -t_1-, which supports the aforementioned conjecture.


[1] Nurdin, E. T. Baskoro, A. N. M. Salman, N. N. Gaos, On the total vertex irregularity strength of trees, Discrete Math., 310 (2010), 3043-3048.
[2] R. Simanjuntak, Susilawati, E. T. Baskoro, Total vertex irregularity strength for trees with many vertices of degree two, Electron. J. Graph Theory Appl. (EJGTA), 8 (2020), 415-421.
[3] Susilawati, E. T. Baskoro, R. Simanjuntak, Total vertex irregularity strength of trees with maximum degree four, AIP Conf Proc., 1707 (2016), 020022.
[4] Susilawati, E. T. Baskoro, R. Simanjuntak, Total vertex irregularity strength of trees with maximum degree five, Electron. J. Graph Theory Appl. (EJGTA), 6 (2018), 250-257.

Keywords: Vertex irregular total -k--labeling- Total vertex irregularity strength- Trees

Topic: MATHEMATICS AND STATISTICS