2.3 The Irregularity Strength of Paths and Cycles It then follows by y properties (1)(3)of the vertex vertex hing.This is s illustrated fors)and in the following thre V(K43)h3456ggo112 dgv987665543210 (w)91113151517171921232527 c(w)91113151618171921232527 degn v121110988766 32 (w)121416182020222424262830323436 c(w)121416182021222524262830323436 品 41.1213 14 15.416417.418,192 6、54. 32,1,0 2(U) 15.17,19,2121,23,25,2727,29,29,3133,35,37,3939,41,43,45 (v)16.17.19.2221.23.25.2728.30.29.3133.35.37.3938.41.43.44 The following corollary then summarizes all results on the irregularity strength of regular complete multipartite graphs. Corollary 2.11.If G is a regular complete multipartite graph of order at least 3. then s(G)= 4 ifG=Krr where r3 is odd 3 otherwise. 2.3 The Irregularity Strength of Paths and Cycles We now turn our attention to two other well-known classes of graphs,namely paths and cycles.The next theorem gives the irregularity strength of all paths. Theorem2.1224.For an integer n≥3， 号ifn0(mod4) s(P)={生史if n is odd (空fn=2(mod4). for 1 i<n-1.First.we
2.3 The Irregularity Strength of Paths and Cycles 17 It then follows by properties (1)–(3) of the vertex coloring c0 that c0 is vertexdistinguishing. This is illustrated for K4.3/, K5.3/ and K4.5/ in the following three tables. V.K4.3// u1 u2 u3 u4 u5 u6 u7 u8 u9 u10 u11 u12 degH v 9 876 6554 3210 c0 .v/ 9 11 13 15 15 17 17 19 21 23 25 27 c0 .v/ 9 11 13 15 16 18 17 19 21 23 25 27 V.K5.3// u1 u2 u3 u4 u5 u6 u7 u8 u9 u10 u11 u12 u13 u14 u15 degH v 12 11 10 9 8 87665 43210 c0 .v/ 12 14 16 18 20 20 22 24 24 26 28 30 32 34 36 c0 .v/ 12 14 16 18 20 21 22 25 24 26 28 30 32 34 36 V.K4.5// u1; u2; u3; u4 u5; u6; u7; u8 u9; u10; u11; u12 u13; u14; u15; u16 u17; u18; u19; u20 degH v 15, 14, 13, 12 12, 11, 10, 9 9, 8, 8, 7 6, 5, 4, 3 3, 2, 1, 0 c0 .v/ 15, 17, 19, 21 21, 23, 25, 27 27, 29, 29, 31 33, 35, 37, 39 39, 41, 43, 45 c0 .v/ 16, 17, 19, 22 21, 23, 25, 27 28, 30, 29, 31 33, 35, 37, 39 38, 41, 43, 44 The following corollary then summarizes all results on the irregularity strength of regular complete multipartite graphs. Corollary 2.11. If G is a regular complete multipartite graph of order at least 3, then s.G/ D 4 if G D Kr;r where r 3 is odd 3 otherwise. 2.3 The Irregularity Strength of Paths and Cycles We now turn our attention to two other well-known classes of graphs, namely paths and cycles. The next theorem gives the irregularity strength of all paths. Theorem 2.12 ([24]). For an integer n 3, s.Pn/ D 8 ˆ< ˆ: n 2 if n 0 .mod 4/ nC1 2 if n is odd nC2 2 if n 2 .mod 4/. Proof. Let Pn D .v1; v2;:::;vn/ and ei D viviC1 for 1 i n 1. First, we establish a lower bound for s.Pn/. If c W E.Pn/ ! N is a vertex-distinguishing edge
18 2 The Irregularity Strength of a Graph coloring with induced vertex coloring,some vertex v.Ifv is an end-vertex,say vj =vi,then c(e1)>n;while if deg vj =2,then either c(ej-1)> n/2orc(e)≥n/2.Thus st(Pa)≥n/2 when n is even and s(Pn)≥(n+l)/2when n is odd.If n =2 (mod 4)and s(Pn)=n/2,thenc'(vi):I sisn=[n]and so c'(v;)is odd,contradicting Proposition 2.1.Hence s(P)>(n+2)/2 when n=2(mod4). Next,we show that each of these lower bounds for s(P.)is also an n upper bound. od 4).thenn=4k for some positive integerk.Define the edge coloring c:EP)→Nby iif1≤i≤2k c(e)= (n-2L」if2k+1≤i≤n-1 For the induced vertex coloringc,we then have 2i-1if1≤i≤2k c()= 2n-2i+2if2k+1≤i≤m. This is illustrated in Fig.2.6 for n=8.Since c is a vertex-distinguishing edge coloring whose largest color is c(exx)=2k n/2,it follows that s(Pn)<n/2 and so s(Pn)=n/2 if n=0 (mod 4). Assume next that n is odd.Then n =2k+1 for some positive integer k.If n=3 (mod 4).then define the edge coloring c:E(P.)N by i if I<i<k c(e)= n+1-2[]ifk+1≤i≤n-1 Then the induced vertex coloringis given by 2i-1if1≤i≤k+1 d)=2n-2i+2ifk+2≤i≤m If n=1 (mod 4),then define the edge coloring c:E(P)N by i if1≤i≤k-1ori=k+1 c(ei)= k+1 if i=k n+1-2[51ifk+2≤i≤n-1 Then the induced vertex coloring c'is given by 2i-1 if1≤i≤k-l 2i if i=kk+1 c(U)= 2i-3 if i=k+2 2n-2i+2ifk+3≤i≤n
18 2 The Irregularity Strength of a Graph coloring with induced vertex coloring c0 , then c0 .vj/ n for some vertex vj. If vj is an end-vertex, say vj D v1, then c.e1/ n; while if deg vj D 2, then either c.ej1/ n=2 or c.ej/ n=2. Thus s.Pn/ n=2 when n is even and s.Pn/ .n C 1/=2 when n is odd. If n 2 .mod 4/ and s.Pn/ D n=2, then fc0 P .vi/ W 1 i ng D Œn and so n iD1 c0 .vi/ is odd, contradicting Proposition 2.1. Hence s.Pn/ .n C 2/=2 when n 2 .mod 4/. Next, we show that each of these lower bounds for s.Pn/ is also an upper bound. If n 0 .mod 4/, then n D 4k for some positive integer k. Define the edge coloring c W E.Pn/ ! N by c.ei/ D ( i if 1 i 2k n 2 i 2 ˘ if 2k C 1 i n 1. For the induced vertex coloring c0 , we then have c0 .vi/ D ( 2i 1 if 1 i 2k 2n 2i C 2 if 2k C 1 i n. This is illustrated in Fig. 2.6 for n D 8. Since c is a vertex-distinguishing edge coloring whose largest color is c.e2k/ D 2k D n=2, it follows that s.Pn/ n=2 and so s.Pn/ D n=2 if n 0 .mod 4/. Assume next that n is odd. Then n D 2k C 1 for some positive integer k. If n 3 .mod 4/, then define the edge coloring c W E.Pn/ ! N by c.ei/ D ( i if 1 i k n C 1 2 ˙ i 2 if k C 1 i n 1. Then the induced vertex coloring c0 is given by c0 .vi/ D ( 2i 1 if 1 i k C 1 2n 2i C 2 if k C 2 i n. If n 1 .mod 4/, then define the edge coloring c W E.Pn/ ! N by c.ei/ D 8 ˆ< ˆ: i if 1 i k 1 or i D k C 1 k C 1 if i D k n C 1 2 ˙ i 2 if k C 2 i n 1. Then the induced vertex coloring c0 is given by c0 .vi/ D 8 ˆˆˆˆ< ˆˆˆˆ: 2i 1 if 1 i k 1 2i if i D k; k C 1 2i 3 if i D k C 2 2n 2i C 2 if k C 3 i n.
2.3 The Iregularity Strength of Paths and Cycles 19 B:①，⑤4⑧4⑥，④，② h:①③，③3⑦4⑥，④，② :①102⑤3⑦4⑧4⊙202⊙ B:①1①2⊙3⑧，⑩，⑨4⑥2⊙2⊙ h0:①T⑤+⑦3⊙6②6D4⑧4⑥2④2② Fig.2.6 Edge colorings of P in the proof of Theorem 2.12 for 6n10 This is illustrated in Fig.2.6 for n=7,9.In each case,c is a vertex-distinguishing edge coloring whose largest color is c(e+)=(n+1)/2.it follows that s(P.)< (n+1)/2 and so s(P )=(n+1)/2 when n is odd. ame thatn(mod 4).Thenn+for some positive integer iifi=1,3…,2k-1 c(e)= i+2ifi=2,4…,2k n-2Lif2k+1≤i≤n-1. Then the induced vertex coloringc is given by 1 if i=1 c(v)= 2i+1if2≤i≤2k 2n-2i+2if2k+1≤i≤n This is illustrated in Fig.2.6 forn=6.10.Since c is a verte -distinguishing edge coloring having the largest color c()=(n+2)/2.it follows that s(P) (n+2)/2 and so s(P)=(n +2)/2 when n 2 (mod 4). The next theorem gives the irregularity strength of cycles (see [411). Theorem2.13.For an integer n≥3， "史fn三1(mod4) s(Cn)if n is even (2.11) fn三3(mod4)
2.3 The Irregularity Strength of Paths and Cycles 19 4 22 7 642 1 234 1 23 4 2 1 23 P7 4 2 2 4 1 43 5 6 5 5 10 6 4 22 4 4 2 2 12 10 8 4 2 P6 P8 P9 1 1 1 P10 3 3 5864 2 7 5 8 592 8 7 9 6 1 3 5 1 1 2 6 4 6 4 2 Fig. 2.6 Edge colorings of Pn in the proof of Theorem 2.12 for 6 n 10 This is illustrated in Fig. 2.6 for n D 7; 9. In each case, c is a vertex-distinguishing edge coloring whose largest color is c.ekC1/ D .n C 1/=2, it follows that s.Pn/ .n C 1/=2 and so s.Pn/ D .n C 1/=2 when n is odd. Finally, assume that n 2 .mod 4/. Then n D 4kC2 for some positive integer k. Define the edge coloring c W E.Pn/ ! N by c.ei/ D 8 ˆ< ˆ: i if i D 1; 3 ; 2k 1 i C 2 if i D 2; 4 ; 2k n 2 i 2 ˘ if 2k C 1 i n 1. Then the induced vertex coloring c0 is given by c0 .vi/ D 8 ˆ< ˆ: 1 if i D 1 2i C 1 if 2 i 2k 2n 2i C 2 if 2k C 1 i n. This is illustrated in Fig. 2.6 for n D 6; 10. Since c is a vertex-distinguishing edge coloring having the largest color c.e2kC1/ D .n C 2/=2, it follows that s.Pn/ .n C 2/=2 and so s.Pn/ D .n C 2/=2 when n 2 .mod 4/. The next theorem gives the irregularity strength of cycles (see [41]). Theorem 2.13. For an integer n 3, s.Cn/ D 8 ˆ< ˆ: nC1 2 if n 1 .mod 4/ nC2 2 if n is even nC3 2 if n 3 .mod 4/. (2.11)
20 2 The Irregularity Strength of a Graph Pof By of the expressions in()isalower bound for s(Cn).Thus,it remains to verify that each of these expressions is also an upper bound.Let Cn =(v1,v2.....Un.Vn+1 v1)where n 2 3. We first consider the case when n 1 (mod 4).Then n 4g 1 for some positive integer g and so=2q+1.Define an edge coloring c:E(C4+1) 2a+1lby 2g+1-2 for1≤i≤2q+1 c(U+1)= i-24 for2g+2≤i≤4g+1. Then the induced vertex coloringcsatisfies the following d()= 4g+4-2iif1≤i≤2g+1 2i-4g-1if2g+2≤i≤4g+1. This is illustrated in Fig.2.7 for C and C.Since c is a vertex-distinguishing edge coloring whose largest color is 2+1.it follows that s(C)2+1 and s s(C4g+1)=3 q十 Next,we show that if n is even,the lower bound for s(C)is also an upper bound.Then n 2k for some integer k>2 and so=k+1.Define an edge coloring c:E(C2)[k+1]by considering two cases,according to whether k is odd ork is even.If k is odd,then let k+1-2L划 for1≤i≤k c(+1)= k+2-2=1 fori=k+1.k+2 i+1-k fork+3≤i≤2k @07 5⑧ ⑩ o /5 6 ⑨ ⑧ 3 3 ⑦ ⑥ 3 ⑤2 Fig.2.7 Edge colorings of Co and Cu
20 2 The Irregularity Strength of a Graph Proof. By Corollaries 2.6 and 2.7, each of the expressions in (2.11) is a lower bound for s.Cn/. Thus, it remains to verify that each of these expressions is also an upper bound. Let Cn D .v1; v2;:::;vn; vnC1 D v1/ where n 3. We first consider the case when n 1 .mod 4/. Then n D 4q C 1 for some positive integer q and so nC1 2 D 2q C 1. Define an edge coloring c W E.C4qC1/ ! Œ2q C 1 by c.viviC1/ D ( 2q C 1 2 i 2 ˘ for 1 i 2q C 1 i 2q for 2q C 2 i 4q C 1. Then the induced vertex coloring c0 satisfies the following c0 .vi/ D ( 4q C 4 2i if 1 i 2q C 1 2i 4q 1 if 2q C 2 i 4q C 1. This is illustrated in Fig. 2.7 for C9 and C13. Since c is a vertex-distinguishing edge coloring whose largest color is 2q C 1, it follows that s.C4qC1/ 2q C 1 and so s.C4qC1/ D 2q C 1. Next, we show that if n is even, the lower bound nC2 2 for s.Cn/ is also an upper bound. Then n D 2k for some integer k 2 and so nC2 2 D k C 1. Define an edge coloring c W E.C2k/ ! Œk C 1 by considering two cases, according to whether k is odd or k is even. If k is odd, then let c.viviC1/ D 8 ˆ< ˆ: k C 1 2 i 2 ˘ for 1 i k k C 2 2 i 2 ˘ D 1 for i D k C 1; k C 2 i C 1 k for k C 3 i 2k 3 4 C9 5 5 10 8 3 3 4 6 1 2 1 2 3 5 7 9 6 7 7 5 5 3 3 1 1 2 3 4 5 14 12 10 8 6 4 3 2 5 7 9 11 13 C13 Fig. 2.7 Edge colorings of C9 and C13
2.3 The Irregularity Strength of Paths and Cycles 21 60 5 4 Cio 4 6 2⊙ Fig.2.8 Edge colorings of Co and C2 Then the induced vertex coloringsatisfies the following 2k+4-2iif1≤i≤k 3 if i=k+1 c()= 2 fi三k+2 if i=k+3 2i-2k+1ifk+4≤i≤2k. This is illustrated in Fig.2.8 for Cio.If k is even,then let k+1-2L」for1≤i≤k c(U+1）= 0i+1-k fork+1≤i≤2 Then the induced vertex coloring c'satisfies the following (2k+4-2i if 1<i<k c(vi)= 2i-2k+1ifk+1≤i≤2k This is illustrated in Fig.2.8 for C.Since cis a vertex-distinguishing edge coloring whose largest color is k +1,it follows that s(C)k+I and so s(C)=k+1. Finally,we consider the case where n is odd and n =3 (mod 4).In this case. n=4g +3 for some positive integer q.Define an edge coloring c:E(C4q+3) [2g+3)by 2g+3-2l」for1≤i≤2g+3 c+1)= i-(2g+2)for2g+4≤i≤4g+2 2g+3 for i=4g+3
2.3 The Irregularity Strength of Paths and Cycles 21 4 6 6 5 4 4 1 1 2 2 7 7 6 5 4 3 5 5 3 3 1 14 13 10 12 8 6 4 3 2 11 9 11 9 12 10 8 6 4 3 2 5 C10 C12 5 7 Fig. 2.8 Edge colorings of C10 and C12 Then the induced vertex coloring c0 satisfies the following c0 .vi/ D 8 ˆˆˆˆˆ< ˆˆˆˆˆ: 2k C 4 2i if 1 i k 3 if i D k C 1 2 if i D k C 2 5 if i D k C 3 2i 2k C 1 if k C 4 i 2k. This is illustrated in Fig. 2.8 for C10. If k is even, then let c.viviC1/ D ( k C 1 2 i 2 ˘ for 1 i k i C 1 k for k C 1 i 2k Then the induced vertex coloring c0 satisfies the following c0 .vi/ D 2k C 4 2i if 1 i k 2i 2k C 1 if k C 1 i 2k. This is illustrated in Fig. 2.8 for C12. Since c is a vertex-distinguishing edge coloring whose largest color is k C 1, it follows that s.C2k/ k C 1 and so s.C2k/ D k C 1. Finally, we consider the case where n is odd and n 3 .mod 4/. In this case, n D 4q C 3 for some positive integer q. Define an edge coloring c W E.C4qC3/ ! Œ2q C 3 by c.viviC1/ D 8 ˆ< ˆ: 2q C 3 2 i 2 ˘ for 1 i 2q C 3 i .2q C 2/ for 2q C 4 i 4q C 2 2q C 3 for i D 4q C 3.