2 The Irregularity Strength of a Graph 空a恩 vertex coloring c of K satishes (2n-2)+(fn/21-1)ifi=1 c()= n+degG.vi if2≤i≤「m/2] (n -1)degcn vi if[n/21+1≤i≤n It then follows by (2.2)that (2n+[n/21-3ifi=1 c()= 2n-i if2≤i≤n. Since the revised edge coloring c of K is vertex-distinguishing.s(K)3 and so s(Kn)=3. 2.2 On the Irregularity Strength of Regular Graphs We saw in Proposition that the iregularity stre ngth of every regular graph of isat least3and in Theorem2 that the the complete graph Ka,n >3,an (n-1)-regular graph,is 3.We now investigate the irregularity strength of regular graphs in more detail.First,we present a lower bound for the irregularity strength of a graph G in terms of the number of vertices of a specific degree in G. Proposition 2.5 (24D.Let G be a connected g raph of order ns3 with minimu degree (G)and max ndegree△(G)conta ining m vertices of degree ifor each integer iwith(G≤i≤△(G.The sG≥max/- i +1:8(G≤i≤△(G) Proof.Suppose that s(G)=s.Let there be given a vertex-distinguishing edge coloring of G with the colors 1.2.....s and let vV(G)where deg v =i.Then the induced vertex color c'(v)satisfiesisc'(v)<si.Hence each vertex of degree i has one of the si-i+1 =i(s -1)+1 induced colors in the set i.i+1.....si and so n;<i(s-1)+1.Therefore, s(G=3≥-I +1 i for each i with8(G≤i≤A(G). If G is a regular graph,then Proposition 2.5 has the following corollary. 8 2 The Irregularity Strength of a Graph for 1 i n. Next, increase the color of each of the edges v1v2; v1v3;:::;v1vd n 2 e by 1, resulting in an edge coloring c using the colors 1, 2, 3. By (2.3), the induced vertex coloring c0 of Kn satisfies c0 .vi/ D 8 ˆˆ< ˆˆ: .2n  2/ C .dn=2e  1/ if i D 1 n C degGn vi if 2 i dn=2e .n  1/ C degGn vi if dn=2e C 1 i n. It then follows by (2.2) that c0 .vi/ D ( 2n C dn=2e  3 if i D 1 2n  i if 2 i n. Since the revised edge coloring c of Kn is vertex-distinguishing, s.Kn/ 3 and so s.Kn/ D 3. 2.2 On the Irregularity Strength of Regular Graphs We saw in Proposition 2.3 that the irregularity strength of every regular graph of order 3 or more is at least 3 and in Theorem 2.4 that the irregularity strength of the complete graph Kn, n 3, an .n  1/-regular graph, is 3. We now investigate the irregularity strength of regular graphs in more detail. First, we present a lower bound for the irregularity strength of a graph G in terms of the number of vertices of a specific degree in G. Proposition 2.5 ([24]). Let G be a connected graph of order n 3 with minimum degree ı.G/ and maximum degree .G/ containing ni vertices of degree i for each integer i with ı.G/ i .G/. Then s.G/ max ni  1 i C 1 W ı.G/ i .G/ : Proof. Suppose that s.G/ D s. Let there be given a vertex-distinguishing edge coloring of G with the colors 1; 2; : : : ;s and let v 2 V.G/ where deg v D i. Then the induced vertex color c0 .v/ satisfies i c0 .v/ si. Hence each vertex of degree i has one of the si  i C 1 D i.s  1/ C 1 induced colors in the set fi; i C 1; : : : ;sig and so ni i.s  1/ C 1. Therefore, s.G/ D s ni  1 i C 1 for each i with ı.G/ i .G/. If G is a regular graph, then Proposition 2.5 has the following corollary.