2.2 On the Irregularity Strength of Regular Graphs 11 S is a vertex color of G except for one color in S.Because S consists of four odd integers and three even integ rs and e odd r(by Pr n21. each of ege3.5.7.9 s the colo tl vertex ofG. =3 and c' 9.Then th of exa x) den witxaRcoloredIandthethrecdgesinecidceatwihyarecolored3.isimpie、 that x and y belong to the same partite set U of G.Thus each vertex belonging to the other partite set W of G is incident with at least one edge colored 1 and at least one edge colored 3.Thus,the colors of the three vertices in W are 5.6 and 7. Since the sum of the colors of the three vertices of w is 18,thethe sum of the colors of the three vertices of U is also 18.which implies that the colors of the thre ssible ho er,since there is a ve refore.s(K33) n0 (K3)=4bu provide inf t the val e of (Kr）for every integer For two disjoint subsets A and B of the vertex set of a graph G.let [A.B]denote the set of edges joining a vertex of A and a vertex of B. Theorem2.9(T24,51]).For an integer r≥2， ∫3 if r is even s(K）= ）4 if r is odd. Proof.Denote the partite sets of G=Kr.rby U={1,2,,4,}andW={w1,w2,,w, By Corollary 2.6,s(G)>3.Assume first that r is even.Then r 2k for some integer k.Define an edge coloring c:E(G)(1,2,3)by (1 if j>iori=jzk+1 c(w)=2ifi=j≤k 3 if i<i. Then the induced vertex coloring 'satisfies the following c(w)= r+(2i-1)if1≤i≤k )r-2+2iifk+1≤i≤2k c'(w)= 3r+1-2iif1≤i≤k 3r-2i ifk+1≤i≤2k Consequently,c':V(G)r.r+1.....3r-1)is vertex-distinguishing.The colorings c and c'are illustrated for K in Fig.2.3.Since c is a vertex-distinguishing edge coloring.it follows that s(G)<3 and so s(G)=3 if r is even.2.2 On the Irregularity Strength of Regular Graphs 11 S is a vertex color of G except for one color in S. Because S consists of four odd integers and three even integers and every graph has an even number of vertices of odd color (by Proposition 2.1), each of the integers 3; 5; 7; 9 is the color of exactly one vertex of G. Suppose that c0 .x/ D 3 and c0 .y/ D 9. Then the three edges incident with x are colored 1 and the three edges incident with y are colored 3. This implies that x and y belong to the same partite set U of G. Thus each vertex belonging to the other partite set W of G is incident with at least one edge colored 1 and at least one edge colored 3. Thus, the colors of the three vertices in W are 5, 6 and 7. Since the sum of the colors of the three vertices of W is 18, the the sum of the colors of the three vertices of U is also 18, which implies that the colors of the three vertices in U are 3, 6 and 9. This is impossible, however, since there is a vertex of W colored 6. Therefore, s.K3;3/ 4. We now show that not only s.K3;3/ D 4 but provide information about the value of s.Kr;r/ for every integer r 2. For two disjoint subsets A and B of the vertex set of a graph G, let ŒA; B denote the set of edges joining a vertex of A and a vertex of B. Theorem 2.9 ([24, 51]). For an integer r 2, s.Kr;r/ D ( 3 if r is even 4 if r is odd. Proof. Denote the partite sets of G D Kr;r by U D fu1; u2;:::; urg and W D fw1;w2;:::;wrg: By Corollary 2.6, s.G/ 3. Assume first that r is even. Then r D 2k for some integer k. Define an edge coloring c W E.G/ ! f1; 2; 3g by c.uiwj/ D 8 ˆ< ˆ: 1 if j > i or i D j k C 1 2 if i D j k 3 if j < i. Then the induced vertex coloring c0 satisfies the following c0 .ui/ D ( r C .2i  1/ if 1 i k r  2 C 2i if k C 1 i 2k c0 .wi/ D ( 3r C 1  2i if 1 i k 3r  2i if k C 1 i 2k. Consequently, c0 W V.G/ ! fr;r C 1; : : : ; 3r  1g is vertex-distinguishing. The colorings c and c0 are illustrated for K4;4 in Fig. 2.3. Since c is a vertex-distinguishing edge coloring, it follows that s.G/ 3 and so s.G/ D 3 if r is even.