Vertex-distinguishing IE-total Colorings of Cycles and Wheels

(College of Mathematics and Information Science,Northwest Normal University, Lanzhou,730070)

Vertex-distinguishing IE-total Colorings of Cycles and Wheels

CHEN XIANG-EN,HE WEN-YU,LI ZE-PENG AND YAO BING

(College of Mathematics and Information Science,Northwest Normal University, Lanzhou,730070)

Communicated by Du Xian-kun

Let G be a simple graph.An IE-total coloring f of G refers to a coloring of the vertices and edges of G so that no two adjacent vertices receive the same color. Let C(u)be the set of colors of vertex u and edges incident to u under f.For an IE-total coloring f of G using k colors,if C(u)C(v)for any two di ff erent vertices u and v of V(G),thenfis called a k-vertex-distinguishing IE-total-coloring of G, or a k-VDIET coloring of G for short.The minimum number of colors required for a VDIET coloring of G is denoted by(G),and is called the VDIET chromatic number of G.We get the VDIET chromatic numbers of cycles and wheels,and propose related conjectures in this paper.

graph,IE-total coloring,vertex-distinguishing IE-total coloring,vertexdistinguishing IE-total chromatic number

1 Introduction and Preliminaries

For an edge coloring(proper or not)of a graph G and a vertex v of G,denote by S(v)the set of colors used to color the edges incident to v.

A proper edge coloring of a graph G is said to be vertex-distinguishing if each pair of vertices is incident to a di ff erent set of colors.In other words,S(u)S(v)whenever uv. A graph G has a vertex-distinguishing proper edge coloring if and only if it has no more than one isolated vertex and no isolated edges.Such a graph is referred to as a vdec-graph. The minimum number of colors required for a vertex-distinguishing proper edge coloringof a vdec-graph G is denoted by(G).The concept of vertex-distinguishing proper edge coloring has been considered in several papers(see[1–7]).

A general edge coloring(not necessarily proper)of a graph G is called vertex-distinguishing if S(u)≠S(v)is required for any two distinct vertices u and v.The point-distinguishing chromatic index of a vdec-graph G,denoted by χ0(G),refers to the minimum number of colors required for a vertex-distinguishing general edge coloring of G.This parameter was introduced by Harary and Plantholt in[8].In spite of the fact that the structure of complete bipartite graph is simple,it seems that the problem of determining χ0(Km,n)is not easy, especially in the case m=n,as documented by papers of Horˇn´ak and Sot´ak[9–10],Zagaglia Salvi[11–12]and Horˇn´ak and Zagaglia Salvi[13].

For a total coloring(proper or not)f of G and a vertex v of G,denote by Cf(v),or simply C(v)if no confusion arises,the set of colors used to color the vertex v as well as the edges incident to v.Let(v)be the complementary set of C(v)in the set of all colors we used.Obviously|C(v)|≤dG(v)+1 and the equality holds if the total coloring is proper.

For a proper total coloring,if C(u)C(v),i.e.,(u)(v)for any two distinct vertices u and v,then the coloring is called vertex-distinguishing(proper)total coloring and the minimum number of colors required for a vertex-distinguishing(proper)total coloring is denoted by χvt(G).This concept has considered in[14–15].In[15],the authors give the following conjecture.

From[15]we know that the above conjecture is valid for complete graphs,complete bipartite graphs,path and cycle,etc.

In this paper we propose a kind of vertex-distinguishing general total coloring.The relationship of this coloring and vertex-distinguishing proper total coloring is similar to the relationship of vertex-distinguishing general edge coloring and vertex-distinguishing proper edge coloring.

When we de fi ne a proper total coloring of a graph G,we need three conditions for a total coloring which are listed as follows∶

Condition(v)∶No two adjacent vertices receive the same color;

Condition(e)∶No two adjacent edges receive the same color;

Condition(i)∶No edge receives the same color as one of its endpoints.

If we only consider the total coloring of the graph G such that the Condition(v)is satis fi ed,then such a coloring is called an IE-total coloring of the graph G.

If f is an IE-total coloring of the graph G using k colors and for all u,v∈V(G),uv, we have C(u)C(v),then f is called a k-vertex-distinguishing IE-total coloring,or a k-VDIET coloring.The minimum number k for which G has a k-VDIET coloring is called the vertex-distinguishing IE-total chromatic number(or VDIET chromatic number)of the graph G and is denoted by

The following proposition is obviously true.

Proof.For a graph G,let nibe the number of the vertices of degree i,δ≤i≤Δ.Suppose that

In Section 2 we consider the VDIET colorings for cycles and paths.The discussions of the VDIET colorings for wheels and fans are long,so we put them into the Section 3.In Section 4 we give two conjectures.

2 Vertex Distinguishing IE-total Chromatic Numbers of Cycle and Path

Theorem 2.1LetCnbe a cycle of ordern(n≥3).Then

Proof.When n=3,4,5,6,the results are obviously true.Let Cn=u1u2u3···unu1.In this proof when we want to give a k-VDIET coloring fnof Cnwith all colors 1,2,···,k,we need only to give(fn(ui−1ui),fn(ui),fn(uiui+1))or fn(ui−1ui)fn(ui)fn(uiui+1)for each i=1,2,···,n,i.e.,

such that

and

If n=7,then

Assume that C7has a 3-VDIET coloring g.Then there are three vertices such that their color sets are{1},{2}and{3},respectively.But no two such vertices are adjacent.So without loss of generality we assume that C(u1)={1},C(u3)={2},C(u5)={3}.As no two adjacent vertices receive the same color,the colors that u2and u4are assigned under g are 3 and 1,respectively.Thereby u2and u4have the same color set,which is a contradiction.So there does not exist a VDIET coloring of C7using 3 colors.

Obviously,

If

i.e.,8≤n≤14,then

Let

If

i.e.,15≤n≤25,then

Let

where“+”denotes the concatenation of sequence.Obviously,when 15≤n≤25,fnis a 5-VDIET coloring of Cn,so the result holds.

We now want to apply the same technique to give fnfor

To do so,we de fi ne Ckat fi rst.Let

If l≡0(mod 4),let

If l≡1(mod 4),let

If l≡2(mod 4),let

If l≡3(mod 4),let

For l=6,7,···,k−2,we do the above work step by step.Finally we obtain.The last term ofis(k−1)1k or k1(k−1).We change the last term(k−1)1k to(k−1)k1 and k1(k−1)to k(k−1)1.And the resulting sequence is denoted by Ck.

Now we determine fnwhen

Suppose

Let

Theorem 2.2For a pathPnof ordern(≥8),if

Proof.If

Actually,based on the k-VDIET coloring fnof Cn=u1u2u3···unu1de fi ned in the above theorem,if we delete the edge which connects two vertices with color sets{4,2}and{4,3}, i.e.,the corresponding terms are 424 and 434,then we can obtain Pnand its k-VDIET coloring when

3 Vertex Distinguishing IE-total Chromatic Numbers of Wheel and Fan

Proof.Let

In this proof,when we want to give a k-VDIET coloring fnof Wn,we always appoint that the colors which we use are 1,2,···,k,the color of u0is k,and then it suffices to give (fn(ui−1ui),fn(u0ui),fn(ui),fn(uiui+1))or fn(ui−1ui)fn(u0ui)fn(ui)fn(uiui+1)for each i=1,2,···,n,equivalently to give

such that fn(ui)fn(ui+1),i=1,2,···,n,and

If n=4,then

Case 1.|C(u0)|=1.Then C(u0)={3},and each C(ui),i=1,2,3,4,is one of{1,2,3}, {2,3},{1,3}.Three subsets can not distinguish 4 vertices.It is a contradiction.

Case 2.|C(u0)|=2.We may suppose C(u0)={3,2}.Then each C(ui),i=1,2,3,4,is one of{1,2,3},{1,2},{1,3},{2}.Let C(u1)={2}.Then the colors of u2and u4are only 1.Thus{C(u2),C(u4)}={{1,2,3},{1,2}}.So C(u3)={1,3}and the color of u3is 2 for ensuring the vertex coloring proper.This is a contradiction.

Case 3.|C(u0)|=3.Of course C(u0)={1,2,3}.Then each C(ui),i=1,2,3,4,is one of{1,2},{2,3},{1,3},{1},{2}.

(a)If{C(u1),C(u2),C(u3),C(u4)}={{1,2},{1,3},{1},{2}},then two vertices which has color sets{1}and{2}are not adjacent.But these two vertices must have the same color.This is a contradiction.

(b)If{C(u1),C(u2),C(u3),C(u4)}={{1,2},{1,3},{2,3},{1}},without loss of generality,we assume C(u1)={1}.Then 1∈C(u2)∩C(u4).Thus C(u3)={2,3},whichyields g(u3)=2.But g(u1)=1,so the color that u2is assigned under g is one of g(u1), g(u3)and g(u0).This is a contradiction.

(c)If{C(u1),C(u2),C(u3),C(u4)}={{1,2},{2,3},{1},{2}},then similar to(a)we can get a contradiction.

(d)If{C(u1),C(u2),C(u3),C(u4)}={{1,2},{1,3},{2,3},{2}},then similar to(b) we can get a contradiction.

(e)If{C(u1),C(u2),C(u3),C(u4)}={{1,3},{2,3},{1},{2}},then similar to(a)we can get a contradiction.

Thus there does not exist a VDIET coloring of W4using 3 colors,so≥4.We can prove=4 by giving a 4-VDIET coloring f4of W4(note that f4(u0)=4)as follows∶f4=(1132,2214,4323,3411).

As the(proper)vertex chromatic number of W5is χ(W5)=4,χievt(W5)≥4.We can show that=4 by giving a 4-VDIET coloring f5of W5as follows∶

Note that

Case 1.|C(u0)|=1.Then C(u0)={3},and each C(ui),i=1,2,···,6,is one of {1,2,3},{2,3},{1,3}.This is a contradiction.

Case 2.|C(u0)|=2.We may suppose C(u0)={3,1}.Then each C(ui),i=1,2,···,6, is one of{1,2,3},{1,2},{2,3},{1}.This is a contradiction.

Case 3.|C(u0)|=3.Then C(u0)={1,2,3},and each C(ui),i=1,2,···,6,is one of{1,2},{2,3},{1,3},{1},{2}.Five subsets do not distinguish six vertices.This is a contradiction.

f13=(1132,2112,2222,2114,4224,4114,4334,4223,3333,3113,3223,3431,1111). It is easy to see that fnis a 4-VDIET coloring of Wnand(Wn)=4 when 7≤n≤13.

Case 1.|C(u0)|=1.Then C(u0)={4},and each C(ui),i=1,2,···,14,is one of {1,4},{2,4},{3,4},{1,2,4},{1,3,4},{2,3,4},{1,2,3,4}.This is a contradiction.

Case 2.|C(u0)|=2.We may suppose C(u0)={1,4}.Then each C(ui),i=1,2,···,14, is one of{1},{1,2},{1,3},{2,4},{3,4},{1,3,4},{1,2,4},{1,2,3},{2,3,4},{1,2,3,4}. This is a contradiction.

Case 3.|C(u0)|=3.We may suppose C(u0)={1,2,4}.Then each C(ui),i= 1,2,···,14,is one of{1},{2},{1,2},{1,3},{1,4},{2,3},{2,4},{3,4},{1,2,3},{1,3,4}, {2,3,4},{1,2,3,4}.This is a contradiction.

Case 4.|C(u0)|=4,that is,C(u0)={1,2,3,4}.Then each C(ui),i=1,2,···,14,is one of{1},{2},{3},{1,2},{1,3},{1,4},{2,3},{2,4},{3,4},{1,2,3},{1,2,4},{1,3,4}, {2,3,4}.This is a contradiction.

f14=(1132,2112,2222,2114,4444,4224,4114,4334,4223,3333,3113,3223,3431,1111).

(I)We prove that what wheel has(k−1)-VDIET coloring with colors 1,2,···,k−1 for k≥6.

Suppose that Wnhas a(k−1)-VDIET coloring g.Let|C(u0)|=i.Denote by mithe number of subsets of{1,2,···,k−1}which can be acted as the color set of some uj(1≤j≤n).Then

This yields that if

(II)Next we prove that k colors can color Wn,so that the coloring is IE-total coloring and is vertex distinguishing when

Assume that we have constructed all fiwith

such that

(1)The fi rst term of fiis 1132;

(2)When

and fn(u0)=l,the fi rst term abcd and the last term a1b1c1d1of fnsatisfy that d1=a=1, c1̸=c and if there are at most 3 di ff erent numbers in{a1,b1,c1,d1}then c1=d1=1;

(3)fqhas used up all 4-combinations,3-combinations,2-combinations and 1-combination of{1,2,···,k−1}except for 1-combination{k−1}.Under fq,C(u0)={1,2,···,k−1}.

Let

and let Cibe the sequence de fi ned in the proof of Theorem 2.1 for i≥7.We change each term abc of Cs,4≤s≤k−1,into akbc,and the resulted sequence is denoted byLetObviously,Dkhasterms.

(A)Let fq+1be the sequence formed by inserting the term(k−1)(k−1)(k−1)(k−1) into the place between(k−1)33(k−1)and(k−1)22(k−1)from fq.

(B)Let

Let

If the(r−1)-th term of Dkis akb(k−1),then we can obtain fq+r+1by adding the fi rst r−1 terms of Dkto fq+1and then adding(k−1)k(k−2)1.

If the(r−1)-th term of Dkis(k−1)kab(but not(k−1)k1s,s≤k−2),then we can obtain fq+r+1by adding the fi rst r−1 terms of Dkto fq+1and then adding bk(k−1)1.

Let

If the(r−1)-th term of Bkis abbk,then we can obtainby adding the fi rst r−1 terms of Bktoand then adding the term k(k−1)11.

If the(r−1)-th term of Bkis of the form kaab(≠k11s,i.e.,a≠1),then we can obtainby adding the fi rst r−1 terms of Bktoand then adding the term bk11.

Theorem 3.2LetFnbe a fan of ordern+1.If3≤ n≤ 4,then(Fn)=3;if5≤n≤13,then

thenχievt(Fn)=k.

Proof.Let

In this proof when we want to give a k-VDIET coloring gnof Fnwith the set of all colors {1,2,···,k},we always appoint that the color of v0is k and then it suffices to give the desired sequence

Assume that F5has a 3-VDIET coloring h and h(v0)=3.

If|C(v0)|=1,then 3∈C(vi),i=0,1,···,5.But the number of the subsets of{1,2,3} which contain 3 is 4.This is a contradiction.

If|C(v0)|≥2,then{3}is not the color set of any vertex.Since the vertex coloring is proper,we may suppose h(v1)=h(v3)=h(v5)=1 and h(v2)=h(v4)=2.As{C(v0), C(v1),···,C(v5)}={{1},{2},{1,2},{1,3},{2,3},{1,2,3}},and C(v3)≠{1},without loss of generality we assume that C(v1)={1}and C(v4)={2}.This yields that 2∈C(vi), i=0,2,3,4,5.This is a contradiction for we just have 4 subsets of{1,2,3}which contain 2.

Similarly to proving that W6has no 3-VDIET coloring in the proof of Theorem 3.1 we can show that F6has no 3-VDIET coloring.And

is a 4-VDIET coloring of F6.So=4.

Similarly to the proof that W14has no 4-VDIET coloring in the proof of Theorem 3.1, we can show that F14have no 4-VDIET coloring.And

g14=(132,2112,2222,2114,4444,4224,4114,4334,4223,3333,3113,3223,3431,111). So

If we delete the fi rst number of the fi rst term of fnand also delete the last number of the last term of fn,then the resulting sequence gnis a 4 or 5-VDIET coloring of Fnwhen 7≤n≤13 or 15≤n≤29.Thus=4 if 7≤n≤13,and=5 if 15≤n≤29. Su

ppose that

and n≥30.

(I)We can show that Fnhas no(k−1)-VDIET coloring.The process is the same as(I) in the proof of Theorem 3.1.So≥k.

(II)If we delete the fi rst number of the fi rst term of fnand also delete the last number of the last term of fn,then the resulting sequence gnis a k-VDIET coloring of Fn.

and n≥30.

The proof is completed.

Theorem 3.3LetKnbe the complete graph of ordern(n≥3),then(Kn)=n.

Proof.Any two vertices in Knmust receive di ff erent colors under arbitrary VDIET coloring.Therefore(Kn)≥n.Of course,we are able to show that(Kn)=n by giving a VDIET coloring of Knusing n colors 1,2,···,n as follows.Assign colors 1,2,···,n to vertices v1,v2,···,vnof Knrespectively,and then let all edges receive the same color 1. The proof is completed.

4 Conjectures

From the results obtained in this paper,we know that for any graph G discussed in this paper but Kn(n≥5),we have χievt(G)=ξ(G)or ξ(G)+1.So we propose the following conjectures.

Conjecture 4.1For a simple graphG,if(proper vertex coloring)chromatic numberχ(G)≤4,we have=ξ(G)orξ(G)+1.

Conjecture 4.2For a simple graphG,we have≤max{ξ(G)+1,χ(G)}.

[1]Balister P N,Bollob´as B,Schelp R H.Vertex distinguishing colorings of graphs with Δ(G)=2. Discrete Math.,2002,252:17–29.

[2]Balister P N,Riordan O M,Schelp R H.Vertex distinguishing edge colorings of graphs.J. Graph Theory,2003,42:95–109.

[3]Bazgan C,Harkat-Benhamdine A,Li H,Wo´zniak M.On the vertex-distinguishing proper edge-colorings of graphs.J.Combin.Theory Ser.B,1999,75:288–301.

[4]Burris A C,Schelp R H.Vertex-distinguishing proper edge-colorings.J.Graph Theory,1997,26(2):73–82.

[5]ˇCer´ny J,Horˇn´ak M.Observability of a graph.Math.Slovaca,1996,46:21–31.

[6]Horˇn´ak M,Sot´ak R.Observability of complete multipartite graphs with equipotent parts.Ars Combin.,1995,41:289–301.

[7]Horˇn´ak M,Sot´ak R.Asymptotic behaviour of the observability of Qn.Discrete Math.,1997,176:139–148.

[8]Harary F,Plantholt M.The Point-distinguishing Chromatic Index.In:Harary F,Maybee J S.Graphs and Application.New York:Wiley Interscience,1985:147–162.

[9]Horˇn´ak M,Sot´ak R.The fi fth jump of the point-distinguishing chromatic index of Kn,n.Ars Combin.,1996,42:233–242.

[10]Horˇn´ak M,Sot´ak R.Localization jumps of the point-distinguishing chromatic index of Kn,n. Discuss.Math.Graph Theory,1997,17:243–251.

[11]Zagaglia Salvi N.On the point-distinguishing chromatic index of Kn,n.Ars Combin.,1988,25B:93–104.

[12]Zagaglia Salvi N.On the value of the point-distinguishing chromatic index of Kn,n.Ars Combin.,1990,29B:235–244.

[13]Horˇn´ak M,Zagaglia Salvi N.On the point-distinguishing chromatic index of complete bipartite graphs.Ars Combin.,2006,80:75–85.

[14]Chen X E.Asymptotic behaviour of the vertex-distinguishing total chromatic numbers of n-cube(in Chinese).J.Northwest Norm.Univ.(Natur.Sci.),2005,41(5):1–3.

[15]Zhang Z F,Qiu P X,Xu B G,et al.Vertex-distinguishing total colorings of graphs.Ars Combin.,2008,87:33–45.

tion:05C15

A

1674-5647(2014)03-0222-15

10.13447/j.1674-5647.2014.03.04

Received date:Oct.18,2011.

Foundation item:The NSF(61163037,61163054)of China and the Scienti fi c Research Project(nwnu-kjcxgc-03-61)of Northwest Normal University.

E-mail address:chenxe@nwnu.edu.cn(Chen X E).