12 2 The Irregularity Strength of a Graph 7 10 2 Next,assume is odd.First,we show that s(G)>4.Assume,to the contrary,that s(G)=3.Then there exists an edge coloring c:E(G){1.2.3) such that V(G)r.r+1.....3r)=T is vertex-distinguishing.Since ITl= 2r+1 and there is an even number of vertices of odd color,there is an even integer tET that is not the color of any vertex in G. If I is subtracted from each edge color,then we obtain a vertex-distinguishing he2→a.1…2.Hence the ot the r of an y vertex of Let V(G) whe re Is r.such that S is the set of verticesof G having the smallestrcolors and L is the set of vertices of G having the largestr colors.Let a(S.L)=>c(e). ee[sL] UL UnL.WL WnL,a IULl and b=WLl.Then a+b=r.If xE UL then∑re.wac(e)≤2bh;while ifx∈WL,then∑eea.ac(e)≤2a.Therefore aS.D≥∑e-2+∑kd-2a=∑cm-4ab Sincea+b=r and r is odd,the maximum value of ab is(r-1).Hence a(S,L)≥ ∑c-2- (2.5) We consider two cases,according to whether isr or ir+2. Case 1.is r.Since c'(x):xL=r+1.r+2.....2r).it follows by (2.5)that a6.0≥(+1+r+2+…+2)--1)=P+r+2 (2.6 2
12 2 The Irregularity Strength of a Graph Fig. 2.3 An edge coloring of K4;4 11 9 6 4 5 7 8 10 1 2 3 Next, assume that r 3 is odd. First, we show that s.G/ 4. Assume, to the contrary, that s.G/ D 3. Then there exists an edge coloring c W E.G/ ! f1; 2; 3g such that c0 W V.G/ ! fr;r C 1; : : : ; 3rg D T is vertex-distinguishing. Since jTj D 2r C 1 and there is an even number of vertices of odd color, there is an even integer t 2 T that is not the color of any vertex in G. If 1 is subtracted from each edge color, then we obtain a vertex-distinguishing edge coloring c W E.G/ ! f1; 2g such that c0 W V.G/ ! f0; 1; : : : ; 2rg. Hence the odd color i D t r is not the color of any vertex of G. Let V.G/ D S [ L, where jSjDjLj D r, such that S is the set of vertices of G having the smallest r colors and L is the set of vertices of G having the largest r colors. Let .S; L/ D X e2ŒS;L c.e/; UL D U \ L, WL D W \ L, a D jULj and b D jWLj. Then a C b D r. If x 2 UL, then P e2Œfxg;WL c.e/ 2b; while if x 2 WL, then P e2Œfxg;UL c.e/ 2a. Therefore, .S; L/ X x2UL Œc0 .x/ 2b C X x2WL Œc0 .x/ 2a D " X x2L c0 .x/ # 4ab: Since a C b D r and r is odd, the maximum value of ab is 1 4 .r2 1/. Hence .S; L/ " X x2L c0 .x/ # .r 2 1/: (2.5) We consider two cases, according to whether i r or i r C 2. Case 1. i r. Since fc0 .x/ W x 2 LgDfr C 1;r C 2;:::; 2rg, it follows by (2.5) that .S; L/ .r C 1 C r C 2 CC 2r/ .r 2 1/ D r2 C r C 2 2 : (2.6)
2.2 On the Irregularity Strength of Regular Graphs 13 On the other hand,c'(x):x S)=0.1.2.....r)i and the sum of these colors is maximum wheni=1.Thus, .0≤0+2+3+…+r=+r-2 2 which contradicts(2.6) Cas 2.i> r +2.Then ((=(rr+1. .2r)-fi and the sum of these colors is minimum wheni=2r-1.It then follows by (2.5)that 8.≥r+(+)+…+2r-2)+2--1》=P-+4 2 (2.7) On the other hand,c'(x):xE S)=0.1.2.....r-1).Hence 8.0≤0+1+2+…+-0=-5 2 which contradicts(2.7).Therefore,s(G)24. It remains to show that there is a vertex-distinguishing edge coloring c:E(G) {1.2.3.4).Since rz 3 is odd,r =2k+1 for some positive integer k.Define an edge coloring c:E(G)1.2.3.4)by (1 if j>iand (i.j)(.) or i=j=k+1 c(uwj)=2 if i=jsk or (i.j)=(k+1.+1) 3ifi=j≥k+2 4 if j<i. Then the induced vertex coloring 'satisfies the following r-2+3iif1≤i≤k+1 c()= r-1+3iifk+2<i<2k+1 [4r+1-3iif1≤i≤k 4r-3i if i=k+1 c(w)= 4r+2-3iifk+2≤i≤2k r+3 ifi=+1. The vertex coloring c:V(G)r.r+1....,4r)is vertex-distinguishing.This is illustrated in Fig.2.4 for Ks.s.Since c is a vertex-distinguishing edge coloring. it follows that s(G)4 and so s(G)=4 ifr is odd
2.2 On the Irregularity Strength of Regular Graphs 13 On the other hand, fc0 .x/ W x 2 SgDf0; 1; 2; : : : ;rgfig and the sum of these colors is maximum when i D 1. Thus, .S; L/ 0 C 2 C 3 CC r D r2 C r 2 2 ; which contradicts (2.6). Case 2. i r C 2. Then fc0 .x/ W x 2 LgDfr;r C 1; : : : ; 2rgfig and the sum of these colors is minimum when i D 2r 1. It then follows by (2.5) that .S; L/ Œr C .r C 1/ CC .2r 2/ C 2r .r 2 1/ D r2 r C 4 2 : (2.7) On the other hand, fc0 .x/ W x 2 SgDf0; 1; 2; : : : ;r 1g. Hence .S; L/ 0 C 1 C 2 CC .r 1/ D r2 r 2 ; which contradicts (2.7). Therefore, s.G/ 4. It remains to show that there is a vertex-distinguishing edge coloring c W E.G/ ! f1; 2; 3; 4g. Since r 3 is odd, r D 2k C 1 for some positive integer k. Define an edge coloring c W E.G/ ! f1; 2; 3; 4g by c.uiwj/ D 8 ˆˆˆˆˆˆ< ˆˆˆˆˆˆ: 1 if j > i and .i; j/ ¤ .k C 1; k C 2/ or i D j D k C 1 2 if i D j k or .i; j/ D .k C 1; 2k C 1/ 3 if i D j k C 2 4 if j < i. Then the induced vertex coloring c0 satisfies the following c0 .ui/ D ( r 2 C 3i if 1 i k C 1 r 1 C 3i if k C 2 i 2k C 1 c0 .wi/ D 8 ˆˆˆˆ< ˆˆˆˆ: 4r C 1 3i if 1 i k 4r 3i if i D k C 1 4r C 2 3i if k C 2 i 2k r C 3 if i D 2k C 1. The vertex coloring c0 W V.G/ ! fr;r C 1; : : : ; 4rg is vertex-distinguishing. This is illustrated in Fig. 2.4 for K5;5. Since c is a vertex-distinguishing edge coloring, it follows that s.G/ 4 and so s.G/ D 4 if r is odd.
14 2 The Irregularity Strength of a Graph 6 9 11 8 1 Fig.2.4 An edge coloring of Ks.s itwas shown that if is a regular complet -partite graph where3. then (G verify this ment by givin th oof Propoition 2n Thoremd h m lie Theorem 2.10.If G is a regular complete k-partite graph where kz3.then sG=3. Proof.Let G=Kin where k >3.Thus G is a (k-1)r-regular graph of order kr. By Proposition 2.3,s(G)>3.Thus,it remains to show that G has a vertex- distinguishing edge coloring using the colors 1.2.3.Let Vi.V2.....V denote thek partite sets of G where %={9,9…0for1≤i≤k First,suppose that r is even,say r =2 for some positive integer We now construct an ordered list L of the n vertices of G,separated into r blocks B1.B2.....B,of k vertices each.The first block is B:vv....v.In general,forl≤j≤(，the blockB,is 6:”y9.…心 (2.8) Fort+1≤j≤r,the block B,is B:,y-,9 (2.9) Consequently,the listLis L:B1,B2.....Be.B+1.Be+2.....Br. (2.10) We relabel the vertices of L as u.u2,.. ..un.Next,we construct a spanning subgraph H of G as follows.For integers i and j with 1 <i<j<n,the vertex is adjacent to u in H ifi+and u and do not belong to the same Partite set of.Thus de≥degn u之…之degand deg=dcgH4+
14 2 The Irregularity Strength of a Graph Fig. 2.4 An edge coloring of K5;5 In [41], it was shown that if G is a regular complete k-partite graph where k 3, then s.G/ D 3. We now verify this statement by giving a proof along the same lines as the proofs of Proposition 2.2 and Theorems 2.4 and 2.8. Theorem 2.10. If G is a regular complete k-partite graph where k 3, then s.G/ D 3: Proof. Let G D Kk.r/ where k 3. Thus G is a .k 1/r-regular graph of order kr. By Proposition 2.3, s.G/ 3. Thus, it remains to show that G has a vertexdistinguishing edge coloring using the colors 1; 2; 3. Let V1; V2;:::; Vk denote the k partite sets of G where Vi D n v.i/ 1 ; v.i/ 2 ;:::;v.i/ r o for 1 i k: First, suppose that r is even, say r D 2` for some positive integer `. We now construct an ordered list L of the n vertices of G, separated into r blocks B1; B2;:::; Br of k vertices each. The first block is B1 W v.1/ 1 ; v.2/ 1 ;:::;v.k/ 1 . In general, for 1 j `, the block Bj is Bj W v.1/ j ; v.2/ j ;:::;v.k/ j : (2.8) For ` C 1 j r, the block Bj is Bj W v.k/ j ; v.k1/ j ;:::;v.2/ j ; v.1/ j : (2.9) Consequently, the list L is L W B1; B2;:::; B`; B`C1; B`C2;:::; Br: (2.10) We relabel the vertices of L as u1; u2;:::; un. Next, we construct a spanning subgraph H of G as follows. For integers i and j with 1 i < j n, the vertex ui is adjacent to uj in H if i C j n C 1 and ui and uj do not belong to the same partite set of G. Thus degH u1 degH u2 degH vn and degH ui D degH uiC1
2.2 On the Irregularity Strength of Regular Graphs 15 ● :· E3:●0 。0● E4:o ● 0●● Es: 0 ● v23u456ggo4112 deg876654432210 (w)81012121416161820202224 281012131417i61820212223 Fig.2.5 Constructing the graph H in K) only when i<n andi=(modk).For G=K3(4)the edge set Es of the graph H is shown in Fig.2.5 where E={uweE(G:i+j≤13}for1≤i≤S First,we define an edge coloring:E(G)1.3)of Gby assigning the color 1 to each edge of H and the color 3 to each edge in G-E(H).The induced vertex coloring c':V(G)N satisfies the following: (1)d(w)is even for all i(1≤i≤n, (2)(u)≤d(2)≤…≤c(un)and (3)(u)=(u+)only when i<n andi=(mod k). We now revise the edge coloring:E(G)(1.3)by constructing a new edge coloring c:E(G)1.2.3)as follows: c(e)+1ife=-t+1k,jeven,2≤j≤(. c(e)= {c(e)-1ife=(g-1k+1,jeven,(+1≤j≤20 E(e) otherwise
2.2 On the Irregularity Strength of Regular Graphs 15 u1 u2 u3 u4 u5 u6 u7 u8 u9 u10 u11 E1 E2 E3 E4 E5 u12 v u1 u2 u3 u4 u5 u6 u7 u8 u9 u10 u11 u12 degH v 876 654 432 210 c (v) 8 10 12 12 14 16 16 18 20 20 22 24 c (v) 8 10 12 13 14 17 16 18 20 21 22 23 Fig. 2.5 Constructing the graph H in K3.4/ only when i < n and i 0 .mod k/. For G D K3.4/, the edge set [5 iD1E5 of the graph H is shown in Fig. 2.5 where Ei D fuiuj 2 E.G/ W i C j 13g for 1 i 5. First, we define an edge coloring c W E.G/ ! f1; 3g of G by assigning the color 1 to each edge of H and the color 3 to each edge in G E.H/. The induced vertex coloring c0 W V.G/ ! N satisfies the following: (1) c0 .ui/ is even for all i (1 i n), (2) c0 .u1/ c0 .u2/ c0 .un/ and (3) c0 .ui/ D c0 .uiC1/ only when i < n and i 0 .mod k/. We now revise the edge coloring c W E.G/ ! f1; 3g by constructing a new edge coloring c W E.G/ ! f1; 2; 3g as follows: c.e/ D 8 ˆˆ< ˆˆ: c.e/ C 1 if e D u.j1/kC1ujk, j even, 2 j `, c.e/ 1 if e D u.j1/kC1ujk, j even, ` C 1 j 2` c.e/ otherwise.
16 2 The Irregularity Strength of a Graph Then the induced vertex coloring:V(G)N satisfies (o)+1ifv=w-w+1,,jeven,.2≤j≤e c() a(w)-1ifv=l-k+,4k,jeven,.e+1≤j≤20 (w) otherwise. erties (1)-(3)of the vertex coloring that c'is vertex- ted for K Fig.5. Next,suppose thatr3 is odd,sayr=2+1 for some positive integer We now construct an ordered list L of the n vertices of G.separated into r blocks B1.B2.....B,of k vertices each.For 1 j+1,the block B is the one in (2.8).For +2 s js r,the block B;is the one in (2.9).Consequently,the list L is as described in (2.10).Then relabel the vertices of L as u.42.. We now construct a spanning subgraph H of G as in the case when r is even.That is.for int iand i with 1<i i< the u;is adja cent to in H 道i+j≤ + and and uj do no ot he long to same pal f G.Thus degH≥degH≥…≥degn v and deg4=degH4+1 only when either i=0(mod)andi≠m.+1kor(②i=[ First,we define an edge coloring:E(G)(1.3)of Gby assigning the color 1 to each edge of H and the color 3 to each edge in G-E(H).The induced vertex coloring c':V(G)N satisfies the following: (1)c(w)is odd for all i(1≤i≤n)ifk-1 is odd and()iseven(l≤i≤m)if I is even. (2)()≤(2)≤…≤t(u)and (3)(w We now revise the edge coloring:E(G)(1,3)by constructing a new edge coloring c E(G)(1.2.3)as follows: (e)+1 if e=uu+iug]or e=g-1k+1k,j=t-i,iodd,1≤i≤- c(e)= (e)-1ife=4g-1w+1u,j=(+i,iodd,3≤i≤t+1 z(e) otherwise. Then the induced vertex coloring c':V(G)N satisfies ((v)+1 if v=uuti,v=uts]or v=-1k+1,,j=t-i.iodd,1≤i≤-1 c(w)= c(w)-1ifv=g-1w+1,4,j=(+i,iodd,3≤i≤t+1 (w) otherwise
16 2 The Irregularity Strength of a Graph Then the induced vertex coloring c0 W V.G/ ! N satisfies c0 .v/ D 8 ˆˆ< ˆˆ: c0 .v/ C 1 if v D u.j1/kC1; ujk, j even, 2 j ` c0 .v/ 1 if v D u.j1/kC1; ujk, j even, ` C 1 j 2` c0 .v/ otherwise. It then follows by properties (1)–(3) of the vertex coloring c0 that c0 is vertexdistinguishing. This is also illustrated for K3.4/ in Fig. 2.5. Next, suppose that r 3 is odd, say r D 2` C 1 for some positive integer `. We now construct an ordered list L of the n vertices of G, separated into r blocks B1; B2;:::; Br of k vertices each. For 1 j ` C 1, the block Bj is the one in (2.8). For ` C 2 j r, the block Bj is the one in (2.9). Consequently, the list L is as described in (2.10). Then relabel the vertices of L as u1; u2;:::; un. We now construct a spanning subgraph H of G as in the case when r is even. That is, for integers i and j with 1 i < j n, the vertex ui is adjacent to uj in H if i C j n C 1 and ui and uj do not belong to the same partite set of G. Thus degH u1 degH u2 degH vn and degH ui D degH uiC1 only when either (1) i 0 .mod k/ and i ¤ n; .` C 1/k or (2) i D ln 2 m : First, we define an edge coloring c W E.G/ ! f1; 3g of G by assigning the color 1 to each edge of H and the color 3 to each edge in G E.H/. The induced vertex coloring c0 W V.G/ ! N satisfies the following: (1) c0 .ui/ is odd for all i (1 i n) if k 1 is odd and c0 .ui/ is even (1 i n) if k 1 is even, (2) c0 .u1/ c0 .u2/ c0 .un/ and (3) c0 .ui/ D c0 .uiC1/ only when either i 0 .mod k/ and i ¤ n; .` C 1/k or i D ˙n 2 . We now revise the edge coloring c W E.G/ ! f1; 3g by constructing a new edge coloring c W E.G/ ! f1; 2; 3g as follows: c.e/ D 8 ˆˆˆˆˆ< ˆˆˆˆˆ: c.e/ C 1 if e D u`kC1ud n 2 e or e D u.j1/kC1ujk, j D ` i, i odd, 1 i ` c.e/ 1 if e D u.j1/kC1ujk, j D ` C i, i odd, 3 i ` C 1 c.e/ otherwise. Then the induced vertex coloring c0 W V.G/ ! N satisfies c0 .v/ D 8 ˆˆˆˆˆ< ˆˆˆˆˆ: c0 .v/ C 1 if v D u`kC1, v D ud n 2 e or v D u.j1/kC1; ujk, j D ` i, i odd, 1 i ` 1 c0 .v/ 1 if v D u.j1/kC1; ujk, j D ` C i, i odd, 3 i ` C 1 c0 .v/ otherwise.