Smarandachely Adjacent-vertex-distinguishing Proper Edge Coloring of K4∨Kn

CHEN Xiang-en,YAO Bing

(College of Mathematics and Statistics,Northwest Normal University,Lanzhou 730070,China)

Smarandachely Adjacent-vertex-distinguishing Proper Edge Coloring of K4∨Kn

CHEN Xiang-en,YAO Bing

(College of Mathematics and Statistics,Northwest Normal University,Lanzhou 730070,China)

Let f be a proper edge coloring of G using k colors.For each x∈V(G),the set of the colors appearing on the edges incident with x is denoted by Sf(x)or simply S(x)if no confusion arise.Ifandfor any two adjacent vertices u and v,then f is called a Smarandachely adjacent vertex distinguishing proper edge coloring using k colors,or k-SA-edge coloring.The minimum number k for which G has a Smarandachely adjacent-vertex-distinguishing proper edge coloring using k colors is called the Smarandachely adjacent-vertex-distinguishing proper edge chromatic number,or SA-edge chromatic number for short,and denoted byχ′sa(G).In this paper,we have discussed the SA-edge chromatic number of K4∨Kn.

complete graphs;join of graphs;Smarandachely adjacent-vertex-distinguishing proper edge coloring;Smarandachely adjacent-vertex-distinguishing proper edge chromatic number

§1. Introduction

Let G be a fi nite,undirected simple graph and denote byΔ(G)the maximum degree of G. Let C={1,2,···,k}be a finite set of colors and let f:E(G)−→C be a k-proper edge coloring of G.The color set ofa vertex x∈V(G)with respect to f,in symbols Sf(x)or simply S(x)if no confusion arise,is the set of colors of edges incident with x,i.e.,Sf(x)={f(e)|e∈ E(G),e is incident with x}.Letis written by S(x)if no confusion arise and S(x)is called the complementary color set of vertex x.

The k-proper edge coloring f of G is called k-adjacent-vertex-distinguishing(k-AVDPEC for short)if it distinguishes any two adjacent vertices by their color sets,i.e.,Sf(u)/=Sf(v)for∀u,v∈V(G),uv∈E(G).Let=min{k|G has a k-AVDPEC}.is called the adjacent-vertex-distinguishing proper edge chromatic number of G.

A graph G(which has at least one edge)has an adjacent-vertex-distinguishing proper edge coloring if and only if G has no isolated edges.

Adjacent-vertex-distinguishing proper edge coloring is considered in[1,3-4].The following conjecture was proposed by the authors of[4]. Conjecture 1 Let G be a simple connected graph with order at least 6,thenΔ(G)+2.

The k-proper edge coloring f of G is called a Smarandachely adjacent vertex distinguishing proper edge coloring or simply k-SA-edge coloring(or SA-edge coloring using k colors),ifandfor any two adjacent vertices u and v.The minimum number k for which G has an SA-edge coloring using k colors is called the Smarandachely adjacent-vertexdistinguishing proper edge chromatic number or SA-edge chromatic number for short,and denoted by

The SA-edge chromatic number ofdouble graph ofpaths,cycles,stars and fans are discussed in[5].

A graph G(which has at least one edge)has an SA-edge coloring if and only if G has no vertices of degree one.

In this paper,the vertices of K4(a graph with order 4 and no edges)are denoted by u1,u2,u3,u4,while the vertices of Kn(the complete graph with order n)are denoted by v1,v2,···,vnifno specialinstruction.The join of K4and Knis denoted by K4∨Kn.In this paper,we have discussed the SA-edge chromatic number of K4∨Knand obtained the following theorem.

The following lemma is obviously true.

Lemma 1.1 If G has at least one edge and no vertices ofdegree one,then

For vertex-distinguishing VE-total colorings of cycle and complete graphs,we can see[6]. For vertex-distinguishing totalcolorings of 2Cn,we can see[7].

Other terminologies and notations will follow that of[2].

§2.Main Results

Proof The maximum degree of K4∨Knis n+3,so≥n+4,by Lemma 1.1.

Case 1 n is an even integer number.

Suppose K4∨Knhas(n+4)-SA-edge coloring,the unique color which is not in S(v1)should be in color sets of all other n+4−1 vertices.But n+3 is an odd number,the set of edges with one given color is a matching.This is a contradiction.So K4∨Knhas no(n+4)-SA-edge coloring.

Case 2 n is an odd integer number.

Suppose K4∨Knhas(n+4)-SA-edge coloring.Let the colors we have used be 1,2,···,n+ 4.There is only one color which is not in S(vj),j=1,2,···,n+4,let S(vj)={j}, j=1,2,···,n.Then{1,2,···,n}⊆S(ui),i=1,2,3,4.So S(ui)={1,2,···,n}, i=1,2,3,4.Thus the edges colored by n+1 are the edges which connected two vertices in {v1,v2,···,vn}.The set of the edges colored by n+1 is a matching,n is an odd number, so n+1 is not in some S(vj).This is a contradiction.So K4∨Knhas no(n+4)-SA-edge coloring.

The proof is completed.

Firstly we prove that K4∨K2has no 8-SA-edge coloring.

Suppose K4∨K2has an 8-SA-edge coloring.Then under this coloring there exists one color,say 1,which has colored two edges.So 1∈S(vj),j=1,2.There exists one S(ui)which contain 1.Without loss of generality we assume S(u1)={1,k},k/=1.Obviously there exists l∈{1,2}such that k∈S(vl).So S(u1)⊆S(vl).A contradiction.

As for K4∨K2has 9-SA-edge coloring,this is obvious because the 9 edges of K4∨K2may receive 9 diff erent colors.

The proof is completed.

Firstly we prove that K4∨K3has no 8-SA-edge coloring.

Suppose that K4∨K3has an 8-SA-edge coloring and the colors used in this coloring are 1,2,···,8.Then each S(ui)is a 3-subset of{1,2,···,8}.

Case 1 |S(u1)∪S(u2)∪S(u3)∪S(u4)|=3,i.e.,S(u1)=S(u2)=S(u3)=S(u4).

Without loss of generality we assume S(ui)={1,2,3},i=1,2,3,4.Then the number of edges colored by 1 is four and the set of edges colored by 1 is a matching.But K4∨K3has exactly 7 vertices.This is a contradiction.

Case 2 |S(u1)∪S(u2)∪S(u3)∪S(u4)|=4.

Without loss of generality we assume S(u1)∪S(u2)∪S(u3)∪S(u4)={1,2,3,4}.The colors of u1v1,u2v1,u3v1,u4v1are different and contained in{1,2,3,4},so{1,2,3,4}⊆S(v1).As S(u1)⊆{1,2,3,4},therefore S(u1)⊆S(v1).This is a contradiction.

Case 3 |S(u1)∪S(u2)∪S(u3)∪S(u4)|=5.

Without loss of generality we assume S(u1)∪S(u2)∪S(u3)∪S(u4)={1,2,3,4,5}.The set of the colors of v1v2,v3v2,v1v3is{6,7,8}.So each S(vi)contains exactly two colors in {6,7,8}and exactly four colors in{1,2,3,4,5}.Thus each Fi=S(vi)∩{1,2,3,4,5}is one of the following 5 sets:

{1,2,3,4},{1,2,3,5},{1,2,4,5},{1,3,4,5},{2,3,4,5}.

As F1∪F2∪F3=S(u1)∪S(u2)∪S(u3)∪S(u4)={1,2,3,4,5},therefore there exist two subsets in F1,F2,F3which are not equal.Without loss of generality we assume F1/=F2.

If there exist two subsets among S(u1),S(u2),S(u3),S(u4)such that the intersection of these two subsets has exact one color,we may assume S(u1)={1,2,3},S(u2)={3,4,5},then one of these two sets is a subset of F1or F2.This is a contradiction.

If the intersection of arbitrary two sets among S(u1),S(u2),S(u3),S(u4)has at least two colors,then at least 3 sets among S(u1),S(u2),S(u3),S(u4)are diff erent each other.Without loss of generality we assume S(u1)={1,2,3},S(u2)={2,3,4}.The set S(ui)(i=3 or 4) which contain 5 is not the sets{5,1,2},{5,1,3},{5,2,4},{5,3,4},{5,1,4}.We may assume S(u3)={5,2,3}.This illustrate that the number of edges colored by i is 3,i=2,3.Thus 2,3/∈S(u4),so S(u4)={1,4,5}.In this time|S(u1)∩S(u4)|=1,a contradiction.

Case 4 |S(u1)∪S(u2)∪S(u3)∪S(u4)|=6.

Without loss of generality we assume S(u1)∪S(u2)∪S(u3)∪S(u4)={1,2,3,4,5,6}.In this time each color in{7,8}has colored only one edge in{v1v2,v1v3,v2v3}.We may assume that the color of the edge in{v1v2,v1v3,v2v3}which is not colored by 7 or 8 is 6.Then the number ofedges connecting the vertices in{u1,u2,u3,u4}and the vertices in{v1,v2,v3}and colored by 6 is one.This illustrate that there are 3 sets in S(u1),S(u2),S(u3),S(u4)which do not contain color 6.Without loss of generality we assume 6∈S(u1),6/∈S(u2)∪S(u3)∪S(u4) and|S(v3)∩{7,8}|=2.Note that each Fj=S(vj)∩{1,2,3,4,5}is one ofthe following 5 sets: {1,2,3,4},{1,2,3,5},{1,2,4,5},{1,3,4,5},{2,3,4,5},j=1,2.

If F1=F2,without loss of generality we assume F1=F2={1,2,3,4}and S(v3)= {1,2,5,6,7,8},then 1,2∈S(vj),j=1,2,3.Thus there exists i∈{1,2,3,4},such that S(ui)={1,2,c}.There exists j∈{1,2,3},such that c∈S(vj).Then we have S(ui)⊆S(vj). This is a contradiction.

We willsuppose that F1/=F2in the following.

Fact 1 If the intersection of some S(ui)and some S(uj)is an empty set,then S(ui)or S(uj)is contained in some S(vk),where|S(vk)∩{7,8}|=1.

If the intersection of two sets in S(u2),S(u3),S(u4)has exactly one color,we may assume S(u2)={1,2,3},S(u3)={1,4,5},then there exist i∈{2,3},there exists j∈{1,2},such that S(ui)⊆Fj⊆S(vj),a contradiction.

If the intersection of any two sets in S(u2),S(u3),S(u4)has at least 2 colors and|S(u2)∪S(u3)∪S(u4)|=3,then S(u1)∩S(u2)=∅.A contradiction may arise by Fact 1.

If the intersection of any two sets in S(u2),S(u3),S(u4)has at least 2 colors and|S(u2)∪S(u3)∪S(u4)|=4,we may assume that S(u2)∪S(u3)∪S(u4)={1,2,3,4},then S(u1)= {5,6,x},x∈{1,2,3,4}.Without loss of generality we assume that S(u2)={1,2,3}, S(u3)={2,3,4}.This illustrate that the number of edges colored by 2(or 3)is 3 and the number of edges colored by 3(or 2)is 2 or the number of edges colored by i is 3,i=2,3. Because the maximum matching has only 3 edges.The number ofedges connecting the vertices in{u1,u2,u3,u4}and the vertices in{v1,v2,v3}and colored by 6 is one.

When x=1,S(u1)={5,6,1},S(u3)={2,3,4},S(u1)∩S(u3)=∅.A contradiction may arise by Fact 1.When x=2,S(u1)={5,6,2},S(u4)={1,3,4},S(u1)∩S(u4)∅. A contradiction may arise by Fact 1.When x=3,S(u1)={5,6,3},S(u4)={1,2,4}, S(u1)∩S(u4)=∅.A contradiction may arise by Fact 1.When x=4,S(u1)={5,6,4}, S(u2)={1,2,3}.A contradiction may arise by Fact 1.

If the intersection of any two sets in S(u2),S(u3),S(u4)has at least 2 colors,and|S(u2)∪S(u3)∪S(u4)|=5,then S(u2)∪S(u3)∪S(u4)={1,2,3,4,5}.Without loss of generality we assume S(u2)={1,2,3},S(u3)={2,3,4},then S(u4)={2,3,5}.In this time S(u1)={1,4,6}or{1,5,6}or{4,5,6}.Thus S(u1)∩S(u4)=∅or S(u1)∩S(u3)=∅or S(u1)∩S(u2)=∅.We can deduce contradiction by Fact 1.

Case 5 |S(u1)∪S(u2)∪S(u3)∪S(u4)|=7.

Without loss of generality we assume S(u1)∪S(u2)∪S(u3)∪S(u4)={1,2,···,7}. While 8 is assigned to only one edge which is in{v1v2,v1v3,v2v1},we may assume that v1v2is colored by 6,v2v3is colored by 7,v1v3is colored by 8.Then{6,7,8}⊆S(v1)∩S(v3), {6,7}⊆S(v2),8/∈S(v2).Only one edge which connects the vertices in{u1,u2,u3,u4}and the vertices in{v1,v2,v3}is colored by i,i=6,7.Suppose that the number of edges which is colored by i is xi,1≤i≤5.Since x1+x2+x3+x4+x5=10,1≤xi≤3,i=1,2,3,4,5, we have{x1,x2,x3,x4,x5}={2,2,2,2,2}or{1,2,2,2,3}or{1,1,2,3,3}.

As S(v2)={1,2,3,4,5,6,7}{i0},i0∈{1,2,3,4,5},we have

Fact 2 S(ui)⊆S(v2)or S(uj)⊆S(v2),when the intersection of some S(ui)and some S(uj)is empty.

There are at least two sets in S(u1),S(u2),S(u3),S(u4)which do not contain 6 or 7. Without loss of generality we assume 6,7/∈S(u1)and 6,7/∈S(u2).

Case 5.1 x1=x2=x3=x4=x5=2.

If S(u1)=S(u2),without loss of generality we assume S(u1)=S(u2)={1,2,3}. Then S(u3)={4,5,6},S(u4)={4,5,7}or S(u3)={4,5,7},S(u4)={4,5,6}.Thus S(u1)∩S(u3)=∅or S(u1)∩S(u4)=∅.A contradiction arise by Fact 2.

If S(u1)and S(u2)have 2 common colors,without loss of generality we assume S(u1)=

{1,2,3},S(u2)={2,3,4},then we will consider the following 3 conditions only in view of the symmetry of S(u3)and S(u4)In the above 3 conditions S(u1)∩S(u2)=∅.So a contradiction may arise by Fact 2.

Conditions 123 S(u3){5,1,4} {5,1,6} {5,1,7} S(u4){5,6,7} {5,4,7} {5,4,6}

If S(u1)and S(u2)have only one common color,without loss of generality we assume S(u1)={1,2,3},S(u2)={3,4,5}.Then S(u3)∪S(u4)={1,2,4,5,6,7}.Thus S(u3)∩S(u4)=∅.A contradiction may arise by Fact 2.

Of course S(u1)and S(u2)must have at least one common color,for S(u1)∪S(u2)⊆{1,2,3,4,5}and|S(u1)|=|S(u2)|=3.

Case 5.2 {x1,x2,x3,x4,x5}={1,2,2,2,3}(As multi-sets).

1)If S(u1)=S(u2),without loss of generality we assume S(u1)=S(u2)={1,2,3}.When S(u3)∩S(u1)=∅or S(u4)∩S(u1)=∅we may obtain contradiction by Fact 2.When S(u3)∩S(u1)/=∅and S(u4)∩S(u1)/=∅,each color is assigned to at most 3 edges which are incident with u1,u2,u3,or u4,so without loss of generality we assume 1∈S(u3),2∈S(u4). In this time x1=3,x2=3.This is a contradiction.

2)If S(u1)and S(u2)have exactly two common colors,without loss ofgenerality we assume S(u1)={1,2,3},S(u2)={2,3,4}.Noting the symmetry of color 2 and 3,1 and 4,while x5≤2,we may assume x1=1 or x5=1.

When x1=1,x2=3,by noting the symmetry of S(u3)and S(u4),we consider the following 3 conditions only.

Conditions 1 2 3 S(u3){5,2,4} {5,2,6} {5,2,7} S(u4) {5,6,7} {5,4,7} {5,4,6}

We have S(u4)∩S(u1)=∅,a contradiction may arise by Fact 2.

When x1=1,x4=3,noting the symmetry of S(u3)and S(u4),we may assume that S(u3)={4,5,6},S(u4)={4,5,7}.So S(u3)∩S(u1)=∅,a contradiction may arise by Fact 2.

When x5=1,x2=3,we have S(u3)∪S(u4)={1,2,4,5,6,7}and then S(u3)∩S(u4)=∅. A contradiction may arise by Fact 2.

When x5=1,x1=3,we will consider the following 3 conditions only in view of the symmetry of S(u3)and S(u4).

In all above conditions we have S(u2)∩S(u4)=∅.A contradiction may arise by Fact 2.

3)If S(u1)and S(u2)have exactly one common color,without loss of generality we assume S(u1)={1,2,3},S(u2)={3,4,5}.In this time,colors 1,2,4,5 are symmetric.So we may assume x1=1 and consider two cases x2=3 and x3=3.

Conditions 1 2 3 S(u3){1,4,5} {1,4,6} {1,4,7} S(u4) {1,6,7} {1,5,7} {1,5,6}

When x2=3,x3=x4=x5=2.We only consider the following 3 conditions in view of the symmetry of S(u3)and S(u4).

Conditions 1 2 3 S(u3){2,4,5} {2,4,6} {2,4,7} S(u4) {2,6,7} {2,5,7} {2,5,6}

For the above first condition,S(u2)∩S(u4)=∅,a contradiction may arise.

For the above second and third condition,S(u1)⊆S(v2)if i0∈{4,5},S(u2)⊆S(v2)if i0=2,S(u4)⊆S(v2)if i0∈{1,3},where S(v2)={1,2,3,4,5,6,7}{i0}.A contradiction may arise.

If x3=3,then x2=x4=x5=2.we have S(u3)∪S(u4)={2,3,4,5,6,7}and then S(u3)∩S(u4)=∅.A contradiction may arise by Fact 2.

4)If the intersection of S(u1)and S(u2)is empty set,then S(u1)⊆S(v2)or S(u2)⊆S(v2), a contradiction.

Case 5.3 {x1,x2,x3,x4,x5}={1,1,2,3,3}.

1)If S(u1)=S(u2),without loss of generality we assume that S(u1)=S(u2)={1,2,3}. Then x4=x5=1.We may assume that x2=x3=3.we have S(u3)∪S(u4)={2,3,4,5,6,7} and then S(u3)∩S(u4)=∅.A contradiction may arise by Fact 2.

2)If S(u1)and S(u2)have exactly two common colors,without loss ofgenerality we assume that S(u1)={1,2,3},S(u2)={2,3,4}.Then x5≤2.Noting the symmetry of 1 and 4,2 and 3,we may assume x1=x4=1 or x1=x5=1.

When x1=x4=1,then x5=2,x2=x3=3,we only consider the following conditions only.

Conditions 1 2 3 S(u3){5,2,3} {5,2,6} {5,2,7} S(u4) {5,6,7} {5,3,7} {5,3,6}

In the first condition,S(u4)⊆S(v2),a contradiction.

In the second and third conditions,S(u4)⊆S(v2)if i0∈{1,2,4};S(u3)⊆S(v2)if i0=3;S(u1)⊆S(v2)if i0=5.We can deduce contradiction.

When x1=x5=1,x4=2,we have x2=x3=3 and S(u3)∪S(u4)={2,3,4,5,6,7}. Thus S(u3)∩S(u4)=∅.A contradiction may arise by Fact 2.

When x1=x5=1,x2=2,we have x3=x4=3.We consider the following conditions only. Obviously we have S(u4)∩S(u1)=∅.This is a contradiction.

Conditions 1 2 3 S(u3){4,3,5} {4,3,6} {4,3,7} S(u4) {4,6,7} {4,5,7} {4,5,6}

3)If S(u1)and S(u2)have exactly one color,without loss of generality we assume S(u1)= {1,2,3},S(u2)={3,4,5}.Noting the symmetry of 1,2,4,5,we may assume x1=x2=1. As 1,2/∈S(u3)∪S(u4)and S(u3)or S(u4)does not contain 3,therefore there exist i∈{3,4}, such that S(u1)∩S(ui)=∅.A contradiction arise.

4)If S(u1)∩S(u2)=∅,then a contradiction arise by Fact 2.

Case 6 If|S(u1)∪S(u2)∪S(u3)∪S(u4)|=8,we may assume that the colors of edge v1v2,v2v3,v3v1are 6,7 and 8 respectively.Then i belongs to exactly one of the sets S(u1),S(u2),S(u3),S(u4),where i∈{6,7,8}.Therefore{6,7,8}⊆S(v1)∩S(v2)∩S(v3).

Case 6.1 When 6,7,8 belong to the same S(ui),without loss of generality we assume that 6,7,8∈S(u1),then the colors of edges u1v1,u1v2,u1v3are 7,8 and 6 respectively.So S(u1)={6,7,8}⊆S(vj),j=1,2,3.A contradiction.

Case 6.2 When there are exactly two colors in{6,7,8}which belong to the same S(ui), without loss of generality we assume that 6,7∈S(u1),then the colors of edges u1v3and u1v1are 6 and 7 respectively.Let S(u1)={6,7,x},x∈{1,2,3,4,5}.There exists j∈{1,2,3}, such that S(u1)⊆S(vj).This is a contradiction.

Case 6.3 Colors 6,7,8 belong to diff erent sets S(ui).

Suppose the number of the edges colored by i is xi,i∈{1,2,3,4,5},then x1+x2+x3+ x4+x5=9 and 1≤ xi≤ 3.Thus{x1,x2,x3,x4,x5}={1,2,2,2,2}or{1,1,2,2,3}or {1,1,1,3,3}.Without loss of generality we assume that 6∈S(u1),7∈S(u2),8∈S(u3).Let Fj=S(uj){6,7,8};Qj=S(vj){6,7,8},j=1,2,3.

If each of two colors in some Fihas been assigned to at least two edges,without loss of generality we assume that F1={1,2}and x1≥2,x2≥2,then there exists j0∈{1,2,3},such that 1,2∈Qj0,i.e.,F1⊆Qj0.So S(u1)⊆S(vj0),a contradiction.

If at least one color in each Fihas been assigned to exactly one edge,without loss of generality we assume i∈Fiand i has been assigned to exactly one edge,i∈{1,2,3}.This illustrate that the number of edges colored by k is three,where k∈{4,5}.In this time 6,7,8/∈S(u4)and 1,2,3/∈S(u4),so S(u4)⊆{4,5}.A contradiction.

Thus K4∨K3has no 8-SA-edge coloring.We will give a 9-SA-edge coloring as follows.

The edges u1v1,u1v2,u1v3are colored by 1,2,3 respectively;The edges u2v1,u2v2,u2v3are colored by 3,4,5 respectively;The edges u3v1,u3v2,u3v3are colored by 4,5,6 respectively; The edges u4v1,u4v2,u4v3are colored by 6,1,2 respectively;The edges v1v2,v2v3,v3v1are colored by 7,8,9 respectively.

For the above proper edge coloring,we have S(u1)={1,2,3},S(u2)={3,4,5},S(u3)= {4,5,6},S(u4)={6,1,2}.S(v1)={1,3,4,6,7,9},S(v2)={2,4,5,1,7,8},S(v3)={3,5,6,2,8, 9}.Arbitrary two sets above don’t contain each other.Thus the above edge coloring is 9-SA-edge coloring of K4∨K3.

The proof is completed.

The proof is completed,

For the above edge coloring,we have S(ui)={6,7,8,9,10},i=1,2,3,4.S(v1)={5,6}, S(v2)={1,7},S(v3)={2,8},S(v4)={3,9},S(v5)={4,10}.Arbitrary two sets above don’t contain each other.Thus the above edge coloring is 10-SA-edge coloring of K4∨K5.

Theorem 2.5 If n≥6 and n is an even integer number,then

Consider the complete graph Kn+4with vertices w1,w2,···,wn+4.Arrange w1,w2,···, wn+3,x,y on the vertices ofa regular(n+5)-gon clockwise and wn+4on the center ofthis regular (n+5)-gon.Note that x and y are not the vertices ofgraph Kn+4.We draw each edge of Kn+4in this regular(n+5)-gon by a line segment.We first color the edges of Kn+4using colors 1,2,···,n+5.The edge wiwn+4and edges which are perpendicular to line segment wiwn+4are colored by i,i=1,2,···,n+3.The edges which are perpendicular to line segment xwn+4are colored by n+4.The edges which are perpendicular to line segment ywn+4are colored by n+5.The resulting coloring is proper.

Based on the above coloring of Kn+4,we can obtain K4∨Knand its edge coloring g by deleting the six edges(their colors arerespectively under original coloring).The com -plementary color sets of all vertices of K4∨Knare given as follows.

In the following we verify that g is an(n+5)-SA-edge coloring of K4∨Kn.

1)If both i and j are odd number,thenThus i=j.

2)If both i and j are even number,thenThus i=j.

3)If i is an odd number,j is an even number,Thus i−1= j,i+1=j,a contradiction.

4)If i is an even number,j is an odd number,Thus i=

j−1,i=j+1,again a contradiction.

So S(wi)and S(wj)do not contain each other when i/=j.

Assume

We have the following 8 cases.

tion:05C15

1002–0462(2014)01–0076–12

Chin.Quart.J.of Math. 2014,29(1):76—87

date:2012-10-08

Supported by NNSF of China(61163037,61163054,61363060)

Biography:CHEN Xiang-en(1965-),male,native of Tianshui,Gansu,a professor of Northwest Normal University,M.S.D.,engages in graph theory with applications.

CLC number:O157.5 Document code:A