2.1 Sum-Defined Vertex Colorings:Irregularity Strength 7 n-iif1≤i≤[n/21 deg v; (2.2 n+1-iif[m/21+1≤i≤n. a盟 each edge ifi≠1，「n/21+1 c(u）= 2degy-1ifi=1,[n/21+1. Since c'is vertex-distinguishing.s(G)2 and so s(G)=2. To show that every complete graph of order n3 has irregularity strength 3 we first make an observation concerning the irregularity strength of every regular graph. Proposition 2.3.The irregularity strength of every regular graph of order 3 or more is at least 3. least 3 wi e color the span ng subgraph of C are color 1.Then H has two ertices u and of equal degree.Since uand v have th same induced color in G.it follows that s(G)>3 Theorem2.424.For each integern≥3，s(Ka）=3 Proof.By Proposition 2.3,it follows that s(K)>3.To establish the inequality s(K)<3,we show that there is a vertex-distinguishing edge coloring of Ka with the colors 1,2 and3.Since the edge coloring of K3 given in Fig.2.1 has this property connected graph of order n4 having ex vertices of equal degree that is described in the proof of Theorem 22.Thus V(Gn)=v1.v2.....v whose degrees are given in (2.2).As noted there,these equal degrees are [n/2].Assign the color 2 to the edges of Gn and the color 1 to the edges of its complement Gn.The induced vertex colors c*(v)for this edge coloring of Kn are then c*(vi)=2degG vi+(n-1-degG vi)=n-1 degg vi (2.3) Fig.2.1 Showing s(K3)=3 4 2
2.1 Sum-Defined Vertex Colorings: Irregularity Strength 7 deg vi D 8 < : n i if 1 i dn=2e n C 1 i if dn=2e C 1 i n. (2.2) So deg vd n 2 e D deg vd n 2 eC1 D bn=2c. Let c be the edge coloring of Gn in which each edge is assigned the color 2 except for v1vd n 2 eC1, which is colored 1. Then c0 .vi/ D 8 < : 2 deg vi if i ¤ 1; dn=2e C 1 2 deg vi 1 if i D 1; dn=2e C 1. Since c0 is vertex-distinguishing, s.G/ 2 and so s.G/ D 2. To show that every complete graph of order n 3 has irregularity strength 3, we first make an observation concerning the irregularity strength of every regular graph. Proposition 2.3. The irregularity strength of every regular graph of order 3 or more is at least 3. Proof. Suppose that there exists an edge coloring of a regular graph G of order at least 3 with the colors 1 and 2 and that H is the spanning subgraph of G whose edges are color 1. Then H has two vertices u and v of equal degree. Since u and v have the same induced color in G, it follows that s.G/ 3. Theorem 2.4 ([24]). For each integer n 3, s.Kn/ D 3. Proof. By Proposition 2.3, it follows that s.Kn/ 3. To establish the inequality s.Kn/ 3, we show that there is a vertex-distinguishing edge coloring of Kn with the colors 1, 2 and 3. Since the edge coloring of K3 given in Fig. 2.1 has this property, we may assume that n 4. Let Gn be the unique connected graph of order n 4 having exactly two vertices of equal degree that is described in the proof of Theorem 2.2. Thus V.Gn/ D fv1; v2;:::;vng whose degrees are given in (2.2). As noted there, these equal degrees are bn=2c. Assign the color 2 to the edges of Gn and the color 1 to the edges of its complement Gn. The induced vertex colors c.vi/ for this edge coloring of Kn are then c.vi/ D 2 degGn vi C .n 1 degGn vi/ D n 1 C degGn vi (2.3) Fig. 2.1 Showing s.K3/ D 3 ... ... .. .. .... ............. .. ..... ........................................ ... ... .. .. .... ............. .. ..... ........................................ ... ... .. .. .... ........... .. .. ... ........................................ ...................................................... ...................................................... 4 3 5 2 1 3
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.
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
10 2 The Irregularity Strength of a Graph Proof.Since it is easy to see that s(C)=3 and K2)=C.we may assume tha r>3.Let G=K).Since G is a (2r-2)-regular graph of order 2r.it follows by Corollary 2.6 that s(G)>3.We show that s(G)<3 by describing a vertex- distinguishing edge coloring c:E(G)(1.2.3). Denote the partite sets of G by Vi.V2.....Vr,where Vi=fxi.yi for I <i r. We now relabel the vertices of G by u.u. u where n=2r.such that ui=x for 1 i<rand u =y for<r.Let H be the spanning subgraph of G where u,yeE(lifl≤i<j≤n and i+j≤n.Thus 2r-1-iif1≤i≤r dcgH= (2.4) 2r-iifr+1≤i≤nm. Thus deg u≥degH2≥·≥degH un and deg ui=deg ur+only when i=r.Next,we define an edge coloring E(G)(1.2.3)of G by assigning the color I to each edge of H and the color 3 to the remaining edges of G.The induced vertex coloring c is then defined by (ui)degu ui +3(2r-2-degu ui)=6r-6-2degn ui forl≤i≤n.Hence(u)≤t(2)≤…≤c(n)with equality only for(,) and c(ur+1).In particular,cu,)=c(u+1)=4r-4. We now revise the edge coloring c by replacing the color 1 of uur by 2. producing a new edge coloring c of G.The induced vertex coloring c'then satisfies the following (2r-1 if i=1 '(ui)= 6r-6-2 degu if2≤i≤r-1orr+1≤i≤n 4r-3 if i=r. This is illustrated for K4 in the following table. 1,42,8294y4为2y1 65433210 68101212141618 c() 78101312141618 Since c is a vertex-distinguishing edge coloring,it follows that s(G)<3 and so s(G)=3. e Even though each complete multipartite graph in which every partite set consists of exactly one vertex or every partite set onsists of exactly two vertices has rity strength 3.this is not the ca ase if every partite set consists of exacty thre vertices,as we now illu with the graph K33.By Corollary 2.1,s(K 3 Assume to the contrary that s(K3.3)=3.Then there is a vertex-distinguisl ng edg coloring c of G =K3.3 with induced vertex coloring c.Therefore,fc(v):v e V(G))S =(3.4.....9).Since the order of G is 6 and |S]7,every integer in
10 2 The Irregularity Strength of a Graph Proof. Since it is easy to see that s.C4/ D 3 and K2.2/ D C4, we may assume that r 3. Let G D Kr.2/. Since G is a .2r 2/-regular graph of order 2r, it follows by Corollary 2.6 that s.G/ 3. We show that s.G/ 3 by describing a vertexdistinguishing edge coloring c W E.G/ ! f1; 2; 3g. Denote the partite sets of G by V1; V2;:::; Vr, where Vi D fxi; yig for 1 i r. We now relabel the vertices of G by u1; u2;:::; un, where n D 2r, such that ui D xi for 1 i r and unC1i D yi for 1 i r. Let H be the spanning subgraph of G where uiuj 2 E.H/ if 1 i < j n and i C j n. Thus degH ui D 8 < : 2r 1 i if 1 i r 2r i if r C 1 i n. (2.4) Thus degH u1 degH u2 degH un and degH ui D degH uiC1 only when i D r. Next, we define an edge coloring c W E.G/ ! f1; 2; 3g of G by assigning the color 1 to each edge of H and the color 3 to the remaining edges of G. The induced vertex coloring c0 is then defined by c0 .ui/ D degH ui C 3.2r 2 degH ui/ D 6r 6 2 degH ui for 1 i n. Hence c0 .u1/ c0 .u2/ c0 .un/ with equality only for c0 .ur/ and c0 .urC1/. In particular, c0 .ur/ D c0 .urC1/ D 4r 4. We now revise the edge coloring c by replacing the color 1 of u1ur by 2, producing a new edge coloring c of G. The induced vertex coloring c0 then satisfies the following c0 .ui/ D 8 ˆˆ< ˆˆ: 2r 1 if i D 1 6r 6 2 degH ui if 2 i r 1 or r C 1 i n 4r 3 if i D r. This is illustrated for K4.2/ in the following table. u1; u2;:::; u8 x1 x2 x3 x4 y4 y3 y2 y1 degH ui 6 5 4 3 3210 c0 .ui/ 6 8 10 12 12 14 16 18 c0 .ui/ 7 8 10 13 12 14 16 18 Since c is a vertex-distinguishing edge coloring, it follows that s.G/ 3 and so s.G/ D 3. Even though each complete multipartite graph in which every partite set consists of exactly one vertex or every partite set consists of exactly two vertices has irregularity strength 3, this is not the case if every partite set consists of exactly three vertices, as we now illustrate with the graph K3;3. By Corollary 2.7, s.K3;3/ 3. Assume to the contrary that s.K3;3/ D 3. Then there is a vertex-distinguishing edge coloring c of G D K3;3 with induced vertex coloring c0 . Therefore, fc0 .v/ W v 2 V.G/g S D f3; 4; : : : ; 9g. Since the order of G is 6 and jSj D 7, every integer in
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.