2.2 On the Irregularity Strength of Regular Graphs 9 Corollary2.624).If G is a connectedr-regular graph.r≥2，of order n≥3 then o≥+1 When n=2 (mod 4)or n=3 (mod 4).Corollary 2.6 can be improved a bit. Corollary 2.7 ((241).If G is a connected r-regular graph of order n z 3 where n三2(mod4)orn三3(mod4).then s(G)>n-1 +1 theenuing oe ing e sol 1.2.....s.Hence each induced vertex color is one of the sr-r+1 colors r.r+ " colo r H ver.n/2of ese co odd.that is The argument when n =3(mod 4)is similar. 学re品四2oR the colors 1.2.....5 shown in Fig.2.2 is vertex-distinguishing,s(P)<5 and so s(P=5. Since.by Theorem 24.s()=3 for every integer n>3.it follows that the h in which e e se ertex has hen each part te set consi of exactly two vertices.For each integerr2,we write K2 for the (2r-2)-regulat complete r-partite graph where each partite set consists of two vertices. Theorem 2.8 ([521).For each integer r z2,s(Kr))=3. colring of 4 1 5 4 5⑨ ⑤2.2 On the Irregularity Strength of Regular Graphs 9 Corollary 2.6 ([24]). If G is a connected r-regular graph, r 2, of order n 3, then s.G/ n  1 r C 1: When n  2 .mod 4/ or n  3 .mod 4/, Corollary 2.6 can be improved a bit. Corollary 2.7 ([24]). If G is a connected r-regular graph of order n 3 where n  2 .mod 4/ or n  3 .mod 4/, then s.G/ > n  1 r C 1: Proof. Suppose that n  2 .mod 4/ and assume, to the contrary, that s.G/ D s D n1 r C 1. Then there is a vertex-distinguishing edge coloring of G with the colors 1; 2; : : : ;s. Hence each induced vertex color is one of the sr  r C 1 colors r;r C 1; : : : ;sr. By assumption, n D sr  r C 1 and so the induced vertex colors are precisely the n colors r;r C 1; : : : ;sr. However, n=2 of these colors are odd, that is, G has an odd number of vertices of odd color, contradicting Proposition 2.1. The argument when n  3 .mod 4/ is similar. By Corollary 2.7, the irregularity strength of the Petersen graph P satisfies s.P/ > 101 3 C 1 D 4, that is, s.P/ 5. Since the edge coloring of the Petersen graph with the colors 1; 2; : : : ; 5 shown in Fig. 2.2 is vertex-distinguishing, s.P/ 5 and so s.P/ D 5. Since, by Theorem 2.4, s.Kn/ D 3 for every integer n 3, it follows that the complete n-partite graph in which every partite set consists of a single vertex has irregularity strength 3. We now see that this is also true when each partite set consists of exactly two vertices. For each integer r 2, we write Kr.2/ for the .2r2/-regular complete r-partite graph where each partite set consists of two vertices. Theorem 2.8 ([52]). For each integer r 2, s.Kr.2// D 3. Fig. 2.2 An edge coloring of the Petersen graph 3 4 10 14 8 13 9 3 5 4 11 3 15 7 1 1 5 5 1 1 5 1 5 2 5