Electronic Journal of Graph Theory and Applications 6 .
, 250Ae257 Total vertex irregularity strength of trees with maximum degree five Susilawati.
Edy Tri BaskoroO .
Rinovia Simanjuntak Combinatorial Mathematics Research Group.
Faculty of Mathematics and Natural Sciences Institut Teknologi Bandung.
Jalan Ganesa 10 Bandung.
Indonesia susilawati nurdin@students.
id, ebaskoro@math.
id, rino@math.
Abstract In 2010.
Nurdin.
Baskoro.
Salman and Gaos conjectured that the total vertex irregularity strength of any tree T is determined only by the number of vertices of degrees 1, 2 and 3 in T .
This paper will confirm this conjecture by considering all trees with maximum degree five.
Furthermore, we also characterize Pi all such trees having the total vertex irregularity strength either t1 , t2 or t3 , where ti = d.
j=1 nj )/.
e and ni is the number of vertices of degree i.
Keywords: irregularity strength, total vertex irregularity strength, tree Mathematics Subject Classification: 05C78, 05C05 DOI: 10.
5614/ejgta.
Introduction In .
Chartrand et al.
proposed the following problem: assign positive integer labels to all the edges of a connected graph of order greater than 2 in such a way that the graph becomes irregular, , the weights .
abel sum.
at all vertices are different.
Find the minimum value of the largest label over all such irregular assignments.
This value is well known as the irregularity strength of the graph.
Motivated by this problem, a survey paper of Gallian .
and a book of Wallis .
Baca et al.
introduced the total vertex irregularity strength of a graph as follows.
Let G(V.
E) be a simple For a labeling PI : V (G) O E(G) Ie .
, 2, 3, .
, .
, the weight of a vertex x is defined as wt.
= I.
xyOOE I.
A labeling I is called a vertex irregular total k-labeling if the Received: 13 July 2017, *Corresponding author.
Revised: 12 January 2018.
Accepted: 27 May 2018.
Total vertex irregularity strength of trees with maximum degree five Susilawati et al.
weights of all vertices are distinct.
The minimum k for which the graph G has a vertex irregular total k-labeling is called the total vertex irregularity strength of G and it is denoted by tvs(G).
Baca et al.
proved that tvs(Cn ) = d n 2 e, n Ou 3.
tvs(Kn ) = 2.
tvs(K1,n ) = d n 1 tvs(Cn y P2 ) = d 4 e.
For a tree T with m pendant vertices and no vertices of degree 2, they proved that d m 1 e O tvs(T ) O m.
They also proved that if G is a .
, .
-graph with minimum p degree and maximum degree OI, then d OI 1 e O tvs(G) O p OI Oe 2 1.
In 2010.
Nurdin.
Baskoro.
Salman and Gaos .
determined the total vertex irregularity strength of trees containing vertices of degree 2, namely a subdivision of a star and a subdivision of a particular caterpillar.
They also improved some of the bounds given in .
and showed that tvs of any tree with n1 pendant vertices and containing no vertices of degree 2 is d n12 1 e.
In the same paper.
Nurdin et al.
also determined the total vertex irregularity strength of trees without vertices of degrees two and three.
They also conjectured that the total vertex irregularity strength of any tree is determined by the number of its vertices of degrees P 1, 2, and 3 only.
Precisely, they conjectured that tvs(T ) = max.
1 , t2 , t3 }, where ti = d.
ij=1 nj )/.
e and ni is the number of vertices of degree i OO .
, .
Many paper studied about the total vertex irregularity strengths of graphs, see .
, 2, 3, 4, 6, 10.
Susilawati.
Baskoro and Simanjuntak .
determined the total vertex irregularity strength for the subdivision of several classes of trees, including the subdivision of a caterpillar, the subdivision of a fire cracker, and the subdivision of an amalgamation of stars.
In other paper .
, they also gave the total vertex irregularity strength of any tree with maximum degree four.
Recently, they studied about total vertex irregularity strength for subdivision of trees .
In this paper, we show that the total vertex irregularity strength of any tree T with maximum degree five is either t1 , t2 or t3 .
This fact strengthens the conjecture of Nurdin et al.
Furthermore, we also characterize all such trees T with the total vertex irregularity strength t1 , t2 or Main Results In this section, we show that the total vertex irregularity strength of any tree with maximum degree five is max.
1 , t2 , t3 }.
This result enhances the conjecture of Nurdin et al.
We also characterize all trees with maximum degree five having the total vertex irregularity strength t1 , t2 or t3 .
To start with, we present the well-known fact regarding P the relationship between the number ni of vertices degree i in any tree T , namely n1 = 2 iOu3 .
Oe .
Theorem 2.
Let T be atree with maximum degree OI.
Let ni be the number of vertices of 1 n1 n2 a n 1 n 1 n n OI degree i.
Then, tvs(T ) Ou max
OI 1
From now on, we will only consider trees with maximum degree five.
For 1 O i O 5, let ni be the number of vertices of degree i and define ti = d.
j=1 nj )/.
By substituting n1 = 2 60 20n2 20n3 40n4 60n5 4 90n5 , t3 = .
Oe .
ni into ti , we obtain that t1 = 90 30n3 60n iOu3 45 15n2 30n3 30n4 45n5 , t4 = 36 12n2 24n603 36n4 36n5 , and t5 = 30 10n2 20n603 30n4 40n5 .
Let Total vertex irregularity strength of trees with maximum degree five Susilawati et al.
qi ti = 60 for i = 1, 2, 3, 4, 5.
Thus, q1 = 90 30n3 60n4 90n5 , q2 = 60 20n2 20n3 40n4 60n5 , q3 = 45 15n2 30n3 30n4 45n5 , q4 = 36 12n2 24n3 36n4 36n5 , and q5 = 30 10n2 20n3 30n4 40n5 .
Now, we start with proving that t4 or t5 cannot be the maximum value of all the values ti s.
Lemma 2.
Let T be a tree with maximum degree five.
Then, t5 O t2 , t5 O t3 and there exists some i OO .
, .
such that t5 O ti .
qi for i = 1, 2, 3, 4, 5.
Then, we have q1 Oe q5 = 60 Oe 10n2 10n3 Proof.
Consider ti = 60 30n4 50n5 , q2 Oe q5 = 30 10n2 10n4 20n5 , q3 Oe q5 = 15 5n2 10n3 5n5 , and q4 Oeq5 = 6 2n2 4n3 6n4 Oe4n5 .
Since q2 Oeq5 and q3 Oeq5 are positive, then t5 O t2 and t5 O t3 .
Now, we need only to show that either q1 Oeq5 or q4 Oeq5 is non negative.
If q1 Oeq5 Ou 0 then the proof concludes, otherwise 60Oe10n2 10n3 30n4 50n5 < 0.
This implies that n2 > 6 n3 3n4 5n5 .
Thus, q4 Oe q5 = 6 2n2 4n3 6n4 Oe 4n5 > 6 2.
n3 3n4 5n5 ) 4n3 6n4 Oe 4n5 = 18 6n3 12n4 6n5 > 0.
Lemma 2.
Let T be a tree with maximum degree five.
Then, there exists some i OO .
, .
such that t4 O ti .
qi Proof.
Consider ti = 60 for i = 1, 2, 3, 4.
Then, we have q1 Oeq4 = 54Oe12n2 6n3 24n4 54n5 and q2 Oeq4 = 24 8n2 Oe4n3 4n4 24n5 .
Thus, we need only to show that either q1 Oeq4 or q2 Oeq4 is non negative.
If q1 Oeq4 Ou 0 then the proof concludes.
Otherwise, 54Oe12n2 6n3 24n4 54n5 < 0, and so n2 > 29 n23 2n4 9n2 5 .
Furthermore, q2 Oe q4 = 24 8n2 Oe 4n3 4n4 24n5 > 24 8( 29 n23 2n4 9n2 5 ) Oe 4n3 4n4 24n5 = 60 20n4 60n5 > 0.
From two above lemmas, we can conclude that max.
1 , t2 , t3 , t4 , t5 } = max.
1 , t2 , t3 }.
The following three lemmas will give the necessary and sufficient conditions for t1 , t2 or t3 to be the maximum value.
Lemma 2.
Let T be a tree with maximum degree five.
1 , t2 , t3 } = t1 if and only if .
n3 Oe 2n4 Oe 3n5 Oe 3 O n2 O 23 n23 n4 3n2 5 ) or ( n22 Oe 3n2 5 Oe 23 O n4 < n3 Oe n22 Oe 3n2 5 Oe 32 ).
Proof.
Consider the following two cases.
Case 1.
t2 Ou t3 .
qi Consider ti = 60 for i = 1, 2, 3.
Since q1 = 90 30n3 60n4 90n5 , q2 = 60 20n2 20n3 40n4 60n5 , q3 = 45 15n2 30n3 30n4 45n5 and t2 Oe t3 Ou 0, then n2 Ou 2n3 Oe 2n4 Oe 3n5 Oe 3.
The fact of max.
1 , t2 , t3 } = t1 implies that t1 Ou t2 , that is 90 30n3 60n4 90n5 Ou 60 20n2 20n3 40n4 60n5 .
This yields that n2 O 23 n23 n4 3n2 5 .
Then, we have 2n3 Oe 2n4 Oe 3n5 Oe 3 O n2 O 32 n23 n4 3n2 5 .
Total vertex irregularity strength of trees with maximum degree five Susilawati et al.
Case 2.
t2 < t3 .
for i = 1, 2, 3.
Since q1 = 90 30n3 60n4 90n5 , q2 = 60 20n2 20n3 Consider ti = 60 40n4 60n5 , q3 = 45 15n2 30n3 30n4 45n5 and t3 Oe t2 > 0, then n3 > 32 n22 n4 3n2 5 .
The fact of max.
1 , t2 , t3 } = t1 implies that t1 Ou t3 , that is 90 30n3 60n4 90n5 Ou 45 15n2 30n3 30n4 45n5 .
This yields that n2 O 3 2n4 3n5 .
Then, we have Oe 3n2 5 Oe 3 O n4 < n3 Oe n22 Oe 3n2 5 Oe 23 .
Then, if max.
1 , t2 , t3 } = t1 we have .
n3 Oe 2n4 Oe 3n5 Oe 3 O n2 O 23 n23 n4 3n2 5 ) or ( n22 Oe 3n2 5 Oe 32 O n4 < n3 Oe n22 Oe 3n2 5 Oe 32 ).
Conversely, by substituting the conditions .
n3 Oe 2n4 Oe 3n5 Oe 3 O n2 O 32 n23 n4 3n2 5 ) or ( n22 Oe 3n2 5 Oe 32 O n4 < n3 Oe n22 Oe 3n2 5 Oe 32 ) into ti = d.
ij=1 nj )/.
e where i OO .
, 2, .
we could obtain max.
1 , t2 , t3 } = t1 .
Lemma 2.
Let T be a tree with maximum degree five.
1 , t2 , t3 } = t2 if and only if ( 23 n4 3n2 5 O n2 O 3 2n4 3n5 ) or .
3 Oe n22 Oe 3n2 5 Oe 32 O n4 < n22 Oe 3n2 5 Oe 23 ).
Proof.
Consider the following two cases.
Case 1.
t1 Ou t3 Consider ti = 60 for i = 1, 2, 3.
Since q1 = 90 30n3 60n4 90n5 , q2 = 60 20n2 20n3 40n4 60n5 , q3 = 45 15n2 30n3 30n4 45n5 , and t1 Oet3 Ou 0 then n2 O 3 2n4 3n5 .
Since max.
1 , t2 , t3 } = t2 , then t2 Ou t1 , that is 60 20n2 20n3 40n4 60n5 Ou 90 30n3 60n4 90n5 .
This yields that n2 Ou 23 n23 n4 3n2 5 .
Then, we have 32 n23 n4 3n2 5 O n2 O 3 2n4 3n5 .
Case 2.
t1 < t3 qi for i = 1, 2, 3.
Since q1 = 90 30n3 60n4 90n5 , q2 = 60 Consider ti = 60 20n2 20n3 40n4 60n5 , q3 = 45 15n2 30n3 30n4 45n5 , and t3 Oe t1 > 0 then n2 > 3 2n4 3n5 .
Since max.
1 , t2 , t3 } = t2 , then t2 Ou t3 , that is 60 20n2 20n3 40n4 60n5 Ou 45 15n2 30n3 30n4 45n5 .
This yields that n3 O 23 n22 n4 3n2 5 .
Then, we have n3 Oe n22 Oe 3n2 5 Oe 32 O n4 < n22 Oe 3n2 5 Oe 32 .
Conversely, by substituting the conditions 32 n23 n4 3n2 5 O n2 O 3 2n4 3n5 or n3 Oe n22 Oe 3n2 5 Oe 32 O n4 < n22 Oe 3n2 5 Oe 32 into ti = d.
ij=1 nj )/.
e where i OO .
, 2, .
we could obtain max.
1 , t2 , t3 } = t2 .
Lemma 2.
Let T be a tree with maximum degree five.
1 , t2 , t3 } = t3 if and only if .
2n4 3n5 O n2 O 23 n23 n4 3n2 5 ) or ( 32 n23 n4 3n2 5 < n2 O 2n3 Oe 2n4 Oe 3n5 Oe .
Proof.
Consider the following two cases.
Case 1.
t1 Ou t2 .
Consider ti = 60 for i = 1, 2, 3.
Since q1 = 90 30n3 60n4 90n5 , q2 = 60 20n2 20n3 40n4 60n5 , q3 = 45 15n2 30n3 30n4 45n5 , and t1 Oet2 Ou 0 then n2 O 23 n23 n4 3n2 5 .
Since Total vertex irregularity strength of trees with maximum degree five Susilawati et al.
1 , t2 , t3 } = t3 , then t3 Ou t1 , that is 45 15n2 30n3 30n4 45n5 Ou 90 30n3 60n4 90n5 .
This yields that n2 Ou 3 2n4 3n5 .
Then, we have 3 2n4 3n5 O n2 O 23 n23 n4 3n2 5 .
Case 2.
t1 < t2 .
qi for i = 1, 2, 3.
Since q1 = 90 30n3 60n4 90n5 , q2 = 60 Consider ti = 60 20n2 20n3 40n4 60n5 , q3 = 45 15n2 30n3 30n4 45n5 , and t2 Oe t1 > 0 then n2 > 23 n23 n4 3n2 5 .
Since max.
1 , t2 , t3 } = t3 , then t3 Ou t2 , that is 45 15n2 30n3 30n4 45n5 Ou 60 20n2 20n3 40n4 60n5 .
This yields that n2 O 2n3 Oe 2n4 Oe 3n5 Oe 3.
Then, we have 32 n23 n4 3n2 5 < n2 O 2n3 Oe 2n4 Oe 3n5 Oe 3.
Conversely, by substituting 3 2n4 3n5 O n2 O 32 n23 n4 3n2 5 or 23 n23 n4 3n2 5 < n2 O 2n3 Oe 2n4 Oe 3n5 Oe 3 into ti = d.
ij=1 nj )/.
e where i OO .
, 2, .
Then, we could obtain max.
1 , t2 , t3 } = t3 .
Next, in Theorem 2.
2, we characterize all trees with maximum degree five such that tvs(T ) = In Theorems 2.
3 and 2.
4, we show a similar characterization for all trees T with tvs(T ) = t2 and tvs(T ) = t3 , respectively.
We call a vertex v OO T an exterior vertex if there exists a pendant vertex in T which is adjacent to v.
The vertices other than exterior and pendant vertices are called interior vertices.
Theorem 2.
Let T be a tree with maximum degree five.
tvs(T ) = t1 if and only if .
n3 Oe 2n4 Oe 3n5 Oe 3 O n2 O 23 n23 n4 3n2 5 ) or ( n22 Oe 3n2 5 Oe 23 O n4 < n3 Oe n22 Oe 3n2 5 Oe 23 ).
Proof.
According to Lemma 2.
3 and Theorem 2.
1, we have tvs(T ) Ou t1 if and only if .
n3 Oe 2n4 Oe 3n5 Oe 3 O n2 O 32 n23 n4 3n2 5 ) or ( n22 Oe 3n2 5 Oe 32 O n4 < n3 Oe n22 Oe 3n2 5 Oe 23 ).
Now, we need to show that tvs(T ) O t1 .
Define a total labeling I : V (T ) O E(T ) Ie .
, 2, .
, t1 } in T by using the following algorithm.
Labeling Algorithm 1 Label all edges e OO E(T ) by the following steps.
Let W = .
1 , w2 , .
, wk } be the set of exterior vertices, where d.
i ) Ou d.
i 1 ) and |E.
i )| Ou |E.
i 1 )| where E.
i ) is the set of pendant edges incident to wi , and d.
i ) is the degreeSof vertices wi , for each i.
Let E1 = ki=1 E.
i ) be an ordered set of all pendant edges in T .
Label the first t1 pendant edges in E1 with .
, 2, 3, .
t1 }, respectively.
Label .
1 Oe t1 ) remaining pendant edges with t1 .
For all the remaining edges e OO E(T ) Oe E1 , we define I.
= t1 .
Label all vertices v OO V (T ) by the following steps.
Total vertex irregularity strength of trees with maximum degree five Susilawati et al.
Let V1 = .
= 1, 2, 3, .
, k and j = 1, 2, 3, .
, ji } be an ordered set of pendant vertices adjacent to wi , where ji is the number of pendant vertices adjacent to wi .
Label the first t1 pendant vertices in V1 with 1.
Label .
1 Oe t1 ) remaining pendant vertices with 2, 3, .
, n1 Oe t1 1.
Denote all non-pendant vertices by y1 , y2 , y3 , .
, yN , where N = P n2 n3 n4 A A A nOI such that s.
1 ) O s.
2 ) O s.
3 ) O A A A O s.
N ), with s.
= I.
, which can be yzOOE(T ) considered as a temporary weight of yi .
Now, define I.
i ) recursively as follows:
1 ) = n1 2 Oe s.
1 ), which implies wt.
1 ) = I.
1 ) s.
1 ).
For 2 O i O N, we define I.
i ) = max.
, wt.
iOe1 ) 1 Oe s.
i )}.
We observe that I is a labeling from V (T )OE(T ) into .
, 2, 3, .
, t1 }, the weights of n1 constitute the set .
, 3, 4, .
, n1 .
, and the weights of all remaining vertices form a sequence n1 2 = wt.
1 ) < wt.
2 ) < wt.
3 ) < A A A < wt.
N ).
Therefore, tvs(T ) O t1 .
Theorem 2.
Let T be a tree with maximum degree five.
tvs(T ) = t2 if and only if ( 23 n23 n4 O n2 O 3 2n4 3n5 ) or .
3 Oe n22 Oe 3n2 5 Oe 32 O n4 < n22 Oe 3n2 5 Oe 32 ).
Proof.
According to Lemma 2.
4 and Theorem 2.
1, we have tvs(T ) Ou t2 if and only if ( 23 n23 n4 3n2 5 O n2 O 3 2n4 3n5 ) or .
3 Oe n22 Oe 3n2 5 Oe 32 O n4 < n22 Oe 3n2 5 Oe 32 ).
Now, we will show that tvs(T ) O t2 .
Let us define a total labeling I : V (T ) O E(T ) Ie .
, 2, .
, t2 } in T by using the Labeling Algorithm 2 for i = 2 as follow.
Labeling Algorithm 2 Label all edges e OO E(T ) by the following steps.
Let W = .
1 , w2 , .
, wk } be the set of exterior vertices, where d.
i ) Ou d.
i 1 ) and |E.
i )| Ou |E.
i 1 )| for i = 1,S2.
A A A , k Oe 1, where E.
i ) is the set of all pendant edges incident to vertex wi .
Let E1 = ki=1 E.
i ) be an ordered set of all pendant edges in T.
Label the first ti pendant edges in E1 with .
, 2, 3, .
, ti }, respectively.
Label .
1 Oe ti ) remaining pendant edges e OO E1 with ti .
Let E2 be the ordered set of non-pendant edges where at least one of the end-vertices of Denote by ei where i = 1, 2, .
, n2 , the edges in E2 and we define I.
i ) = d 1 n31 i e.
Label all remaining edges e OO E(T ) Oe E1 (T ) Oe E2 (T ) with ti .
Total vertex irregularity strength of trees with maximum degree five Susilawati et al.
Label all vertices v OO V (T ) by the following steps.
Let V1 = .
= 1, 2, 3, .
, k and j = 1, 2, 3, .
, ji } be an ordered set of pendant vertices adjacent to wi , where ji is the number of pendant vertices adjacent to wi .
Label the first ti pendant vertices in V1 with 1.
Label the .
1 Oe ti ) remaining pendant vertices with 2, 3, 4, .
, n1 Oe ti 1.
Denote all non-pendant vertices by y1 , y2 , y3 , .
, yN , where N = P n2 n3 n4 A A A nOI , such that s.
1 ) O s.
2 ) O s.
3 ) O A A A O s.
N ), with s.
= I.
, which can be yzOOE(T ) considered as a temporary weight of yi .
We define I.
i ) recursively as follows.
1 ) = n1 2 Oe s.
1 ), which implies wt.
1 ) = I.
1 ) s.
1 ).
For 2 O i O N.
i ) = max.
, wt.
iOe1 ) 1 Oe s.
i )}.
We conclude that I is a labeling from V (T ) O E(T ) into .
, 2, .
, t2 }, and the weights of all pendant vertices constitute the set .
, 3, 4, .
, n1 .
, and the weights of all remaining vertices form a sequence n1 2 = wt.
1 ) < wt.
2 ) < A A A < wt.
N ).
Therefore, tvs(T ) O t2 .
Theorem 2.
Let T be a tree with maximum degree five.
tvs(T ) = t3 if and only if .
2n4 3n5 O n2 O 32 n23 n4 3n2 5 ) or ( 32 n23 n4 3n2 5 < n2 O 2n3 Oe 2n4 Oe 3n5 Oe .
Proof.
According to Lemma 2.
5 and Theorem 2.
1, we have tvs(T ) Ou t3 if and only if .
2n4 3n5 O n2 O 32 n23 n4 3n2 5 ) or ( 32 n23 n4 3n2 5 < n2 O 2n3 Oe 2n4 Oe 3n5 Oe .
Now, we will show that tvs(T ) O t3 , by defining a total labeling I : V (T ) O E(T ) Ie .
, 2, 3, .
, t3 } in T and using the Labeling Algorithm 2 for i = 3.
We conclude that I is a labeling from V (T ) O E(T ) into .
, 2, .
, t3 }, and the weights of all pendant vertices constitute the set .
, 3, 4, .
, n1 .
, and the weights of all remaining vertices form a sequence n1 2 = wt.
1 ) < wt.
2 ) < A A A < wt.
N ).
Therefore, tvs(T ) O t3 .
Conclusion In this paper, we prove that for any tree T with maximum degree five, the total vertex irregularity strength of this tree T is max.
1 , t2 , t3 }.
This fact strengthens the conjecture of Nurdin et .
Moreover, we give necessary and sufficient conditions for all trees T with maximum degree five such that the total vertex irregularity strength is either t1 , t2 or t3 .
To conclude this paper, we give an open problem below.
Open Problem 3.
Find the total vertex irregularity strength of a tree with maximum degree at Acknowledgement This research was supported by the Research Grant AyProgram Riset Inovasi KK ITBAy and AyProgram PMDSUAy.
Ministry of Research.
Technology and Higher Education.
Indonesia.
Total vertex irregularity strength of trees with maximum degree five Susilawati et al.
References