[PDF] [PDF] On the adjacent vertex distinguishing proper edge - Atlantis Press

[PDF] Adjacent vertex-distinguishing proper edge-coloring of strong

Let G be a finite, simple, undirected and connected graph The adjacent vertex- distinguishing proper edge-coloring is the minimum number of colors required for  

[PDF] Graph Theory Graph Adjacent, Nonadjacent, Incident Degree of Graph

Vertices) connected by Lines (called Edges) ▫ Graphs are denoted by uppercase letters such as G Then the set of vertices of a graph G is denoted 

Adjacent vertex-distinguishing edge coloring of graphs

Abstract An adjacent vertex-distinguishing edge coloring (AVD-coloring) of a graph is a proper edge coloring such that no two neighbors are adjacent to the

[PDF] Graph Theory

of its vertex set, and the size of a graph is the cardinality of its edge set Given two vertices u and v, if uv ∈ E, then u and v are said to be adjacent In this case, u 

[PDF] Graph Theory

Two vertices are called adjacent if there is an edge between them The degree of a vertex in an undirected graph is the number of edges associated with it If a 

[PDF] On the adjacent vertex distinguishing proper edge - Atlantis Press

Abstract–A proper k-edge coloring of a graph G is an assignment of k colors, 1, 2, ··· ,k, to edges of G For a proper edge coloring f of G and any vertex x of G, we

[PDF] Graph Theory Notes - University of Warwick

[Adjacency, neighbourhood, vertex degree] Let u, v be two vertices of a graph G • If uv ∈ E(G), then u, v are said to be adjacent, in which case we also say that 

[PDF] On the adjacent vertex distinguishing total coloring numbers - CORE

Let G be a finite simple graph with no component K2 Let C be a finite set of colors and let : E(G) → C be a proper edge coloring of G The color set of a vertex v 

[PDF] Graph Theory

Further definitions The degree of vertex v is the number of edges incident with v Loops are counted twice A set of pairwise adjacent vertices in a graph is called

[PDF] adjacent vertices meaning in english

[PDF] adjacent_vertices boost graph

[PDF] adjectif masculin et feminin pdf

[PDF] adjectif possessif demonstratif exercices

[PDF] adjectif possessif et demonstratif exercices

[PDF] adjectif possessif et démonstratifs

[PDF] adjectif possessif exercises

[PDF] adjectif possessifs exercices pdf

[PDF] adjectif pour décrire le ciel

[PDF] adjectif pour décrire le front

[PDF] adjectif pour décrire le nez

[PDF] adjectif pour décrire le physique d'une personne

[PDF] adjectif pour décrire le printemps

[PDF] adjectif pour decrire le soleil

[PDF] adjectif pour décrire le visage

Onthe adjacent vertex distinguishing proper edge colorings of several classes of complete 4-partite and 5-partite graphs

Xiang-en Chen, Chunyan Ma, Fang Yang, Bing Yao

College of Mathematics and Statistics

Northwest Normal University

Lanzhou, 730070, China

e-mail: chenxe@nwnu.edu.cn e-mail: bjau2008ok@163.com

Abstract-A properk-edge coloring of a graphGis an

assignment ofkcolors,1;2;···;k, to edges ofG. For a proper edge coloringfofGand any vertexxofG, we useS(x)denote the set of the colors assigned to the edges incident tox. If for any two adjacent verticesuandvofG, we haveS(u)̸=S(v), thenfis called the adjacent vertex distinguishing proper edge coloring ofG(or AVDPEC of Gin brief). The minimum number of colors required in an AVDPEC ofGis called the adjacent vertex distinguishing proper edge chromatic number ofG, denoted by′ a(G). In this paper, adjacent vertex distinguishing proper edge chromatic numbers of several classes of complete 4-partite and 5-partite graphs are obtained.(Abstract) Keywords-complete 4-partite graphs; complete 5-partite graphs; proper edge coloring; adjacent vertex-distinguishing proper edge coloring (key words)

I. INTRODUCTION

The graph coloring has a wide range of applications in real life. In[1]-[6], the vertex distinguishing proper edge coloring of graphs is introduced and investigated; In[7], the adjacent vertex distinguishing proper edge coloring of graphs is introduced and investigated and the adjacent vertex distinguishing proper edge chromatic number of a graphG has been obtained for certain graphs, such as cycles, complete graphs. We use the usual notation as can be found in any book on graph theory, see e.g.[9].

LetGbe a simple finite graph with maximum degree

∆(G),kbe a positive integer andfbe an edge coloring (i.e.,fbe an assignment ofkcolors,1;2;···;k, to the edges ofG). For each elementz∈E(G), we usef(z) denote the color of z. For every vertexx∈V(G)the set of colors of edges incident withxis denoted by S(x)and is called the color set ofx. Iffis proper and S(u)̸=S(v)for each edgeuv∈E(G), thenfis called ak- adjacent vertex distinguishing proper edge coloringof

G(or ak-AVDPEC). The minimum number of

colors required in an AVDPEC ofGis called the adjacent vertex distinguishing proper edge chromatic numberofG, denoted by′ a(G).LetG(V;E)be a simple graph and the vertex setV(G)can be partitioned intonstable setsV1;V2;···;Vn, whereVi= v ij|j= 1;2;···;mi},mi=|Vi|;i= 1;2;···;n:If each vertex inViis adjacent to any one vertex inVj, where i̸=j; i;j= 1;2;···;n, thenGis called a completen-partite graph and denoted byKm1;m2;;mn.

Lemma 1.1 and Lemma 1.2 are obvious.

Lemma 1.1For any graphGthat has no isolated edge and at most 1 isolated vertex , we have′ a(G)6′s(G).

Lemma 1.2Ifm>n>p>q>1, then∆(Km;n;p;q) =

m+n+p.

Lemma 1.3

[7]LetGbe a simple connected graph with order at least 3, ifGhas 2 adjacent vertices of maximum degree, then′ a(G)>∆(G) + 1.

Lemma 1.4

[10]LetG[{v|d(v) = ∆(G)}]be an induced subgraph by all vertices of maximum degree inG. IfG[{v| d(v) = ∆(G)}]is a forest, then′(G) = ∆(G). In [8] Zhao Xinmei et al have obtained the adjacent ver- tex distinguishing proper edge chromatic numbers of some complete 4-partite graphs. The results in [8] are listed in the following table: TABLE1: The adjacent vertex distinguishing proper edge chromatic numbers of some complete 4-partite graphs given in [8]graphGcondition a(G)K m;n;p;qm > n > p > q>1m+n+pK n; 1 ;1;1n>2n+ 3 K m;n;1;1m > n>2m+n+ 2 K n;n;n;pn>p+

2andp>23n

K n;n;p;pn>p+

1andp>12n+p+

1 K n;p;p;pn>p+

2andp>2n+

2 p+ 1K n;n;n;n1n>23n K n;n1;n1;n1n>33n-1Based on the above work we will obtain the adjacent vertex distinguishing proper edge chromatic numbers of other several

classes of complete 4-partite and 5-partite graphs in this paper.Proceedings of the 2nd International Symposium on Computer, Communication, Control and Automation (ISCCCA-13)Published by Atlantis Press, Paris, France.

© the authors, 2013

0128

II. MAINRESULTS

Supposek;lare integers,l>1, we use symbol(k)lto

denote the number in{1;2;···;l}which is congruent tok.

For example,(-3)8= 5,(9)8= 1,(20)8= 4.

Theorem 2.1Ifm>n > p>1andm+p62n,

then′ a(Km;n;n;p) =m+ 2n. ProofObviously we have′a(Km;n;n;p)>∆(Km;n;n;p) = m+ 2n:In order to prove′a(Km;n;n;p) =m+ 2n, we need only to give the(m+2n)-AVDPEC ofKm;n;n;p. Suppose the colors that we will use are1;2;···;m+ 2n.

Let edgev4iv3jreceive color(i+j-1)m+2nand edge

v 4 iv2jreceive color(n+i+j-1)m+2n,i= 1;2;···;p;j= 1 ;2;···;n.

Let edgev4iv1jreceive color(2n+i+j-1)m+2n,i=

1 ;2;···;p;j= 1;2;···;m.

Let edgev3iv2jreceive color(m+p+i+j-1)m+2n,

i;j= 1;2;···;n.

Let edgev3iv1jreceive color(p+i+j-1)m+2nand

edgev2iv1jreceive color(m+n+p+i+j-1)m+2n,i= 1 ;2;···;n;j= 1;2;···;m. We construct a cycleCsuch that vertex set ofCism+2n colors{1;2;···;m+2n}and edge set ofCis{(i)m+2n(i+ 1) m+2n|i= 1;2;···;m+ 2n}.

The color setS(v4i)contains allm+ 2ncolors,i=

1 ;2;···;p.

The color setS(v3i)contains justm+n+pcolors from

(i)m+2nto(m+n+p+i-1)m+2nalong cycleC,i= 1 ;2;···;n.

The color setS(v2i)contains justm+n+pcolors which

are divided into two parts, the first part is from(n+i)m+2n to(n+p+i-1)m+2nalong cycleC, the second part is from (m+p+i)m+2nto(2m+n+p+i-1)m+2nalong cycle

C,i= 1;2;···;n.

Note thatS(v2i)contains colors from(n+i)m+2nto(3n+ p+i-1)m+2nwhenm=n,i= 1;2;···;n. The color setS(v1i)contains just2n+pcolors which are divided into three parts, the first part is from(p+i)m+2nto (n+p+i-1)m+2nalong cycleC, the second part is from (2 n+i)m+2nto(2n+p+i-1)m+2nalong cycleCand the third part is from(m+n+p+i)m+2nto(m+2n+p+i- 1) m+2nalong cycleC,i= 1;2;···;m.

From the above discussions we can see that:

1. The number of the colors in each color setC(x)is equal

to the degree of vertexx;

2. The color sets of any two adjacent vertices with the same

degree are different.

Thus the resulting coloring is a(m+ 2n)-AVDPEC of

K m;n;n;p. The proof is completed.

Theorem 2.2Ifm>n > p>1, then′

a(Km;m;n;p) = 2 m+n. ProofObviously we have′a(Km;m;n;p)>∆(Km;m;n;p) = 2 m+n:In order to prove′a(Km;m;n;p) = 2m+n, we need only to give the(2m+n)-AVDPEC ofKm;m;n;p. Suppose the colors that we will use are1;2;···;2m+n.We assign color(i+j-1)2m+nto edgev4iv3j,i= 1 ;2;···;p;j= 1;2;···;n.

We assign color(n+i+j-1)2m+nto edgev4iv2j,i=

1 ;2;···;p;j= 1;2;···;m.

We assign color(n+m+i+j-1)2m+nto edgev4iv1j,

i= 1;2;···;p;j= 1;2;···;m.

We assign color(m+p+i+j-1)2m+nto edgev3iv2j,

i= 1;2;···;n;j= 1;2;···;m.

We assign color(p+i+j-1)2m+nto edgev3iv1j,i=

1 ;2;···;n;j= 1;2;···;m.

We assign color(m+n+p+i+j-1)2m+nto edgev2iv1j,

i;j= 1;2;···;m. We construct a cycleCsuch that vertex set ofCis2m+n colors{1;2;···;2m+n}and edge set ofCis{(i)2m+n(i+ 1) 2 m +n|i= 1;2;···;2m+n}.

The color setS(v4i)contains all2m+ncolors,i=

1 ;2;···;p.

The color setS(v3i)contains just2m+pcolors from

i)2m+nto(2m+p+i-1)2m+nalong cycleC,i= 1 ;2;···;n.

The color setS(v2i)contains justm+n+pcolors which

are divided into two parts, the first part is from(n+i)2m+n to(n+p+i-1)2m+nalong cycleC, the second part is from m+p+i)2m+nto(2m+n+p+i-1)2m+nalong cycle

C,i= 1;2;···;m.

Note thatS(v2i)contains colors from(n+i)2m+nto(3n+ p+i-1)2m+nwhenm=n,i= 1;2;···;m.

The color setS(v1i)contains justm+n+pcolors which

are divided into two parts, the first part is from(p+i)2m+n to(n+p+i-1)2m+nalong cycleC, the second part(m+ n+i)2m+nto(2m+n+p+i-1)2m+nalong cycleC, i= 1;2;···;m.

From the above discussions we can see that:

1. The number of the colors in each color setC(x)is equal

to the degree of vertexx;

2. The color sets of any two adjacent vertices with the same

degree are different.

Thus the resulting coloring is a(2m+n)-AVDPEC of

K m;m;n;p. The proof is completed.

Theorem 2.3Ifn >1, then′

a(Kn;1;1;1;1) =n+ 4. ProofObviously we have∆(Kn;1;1;1;1) =n+3. By Lemma

1.3,′

a(Kn;1;1;1;1)>∆(Kn;1;1;1;1) + 1 =n+ 4:In order to prove′a(Kn;1;1;1;1) =n+4, we need only to give the(n+4)- AVDPEC ofKn;1;1;1;1. Suppose the colors that we will use are1;2;···;n+ 4. We assign color1;2;3respectively to edgesv51v41,v51v31 andv51v21. We assign color(i+3)n+4to edgev51v1i(i= 1;2;···;n).

We assign color3;4respectively to edgesv41v31and

v

41v21.

We assign color(i+4)n+4to edgev41v1i,i= 1;2;···;n.

We assign color5to edgev31v21.

We assign color(i+5)n+4to edgev31v1i,i= 1;2;···;n.

We assign color(i+6)n+4to edgev21v1i,i= 1;2;···;n.Proceedings of the 2nd International Symposium on Computer, Communication, Control and Automation (ISCCCA-13)Published by Atlantis Press, Paris, France.

© the authors, 2013

0129
We construct a cycleCsuch that vertex set ofCisn+ 4 colors{1;2;···;n+ 4}and edge set ofCis{(i)n+4(i+ 1) n+4|i= 1;2;···;n+ 4}. The color setS(v51)contains justn+3colors from(1)n+4 to(n+ 3)n+4along cycleC. The color setS(v41)contains justn+ 3colors which are divided into two parts, the first part is{1}, the second part is from(3)n+4to(n+ 4)n+4along cycleC. The color setS(v31)contains justn+ 3colors which are divided into two parts, the first part is from 2 to 3 along cycle C, the second part is from(5)n+4to(n+ 5)n+4along cycle C. The color setS(v21)contains justn+ 3colors which are divided into two parts, the first part is from3to5along cycle C, the second part is from(7)n+4to(n+ 6)n+4along cycle C. The color setS(v1i)contains just4colors from(i+3)n+4 to(i+ 6)n+4along cycleC,i= 1;2;···;n.

From the above discussions we can see that:

1. The number of the colors in each color setC(x)is equal

to the degree of vertexx;

2. The color sets of any two adjacent vertices with the same

degree are different.

Thus the resulting coloring is a(n+ 4)-AVDPEC of

K n; 1 ;1;1;1. The proof is completed.

Theorem 2.4Ifm > n >1, then′

a(Km;n;1;1;1) =m+ n+ 3. ProofObviously we have∆(Km;n;1;1;1) =m+n+ 2. By Lemma 1.3,′a(Km;n;1;1;1)>∆(Km;n;1;1;1) + 1 =m+n+ 3 :In order to prove′a(Km;n;1;1;1) =m+n+ 3, we need only to give the(m+n+3)-AVDPEC ofKm;n;1;1;1. Suppose the colors that we will use are1;2;···;m+n+ 3. We assign color1;2respectively to edgesv51v41,v51v31.

We assign color(i+ 2)m+n+3to edgev51v2i,i=

1 ;2;···;n.

We assign color(n+i+ 2)m+n+3to edgev51v1i,i=

1 ;2;···;m.

We assign color3to edgev41v31.

We assign color(i+ 3)m+n+3to edgev41v2i,i=

1 ;2;···;n.

We assign color(n+i+ 3)m+n+3to edgev41v1i,i=

1 ;2;···;m.

We assign color(i+ 4)m+n+3to edgev31v2i,i=

1 ;2;···;n.

We assign color(n+i+ 4)m+n+3to edgev31v1i,i=

1 ;2;···;m.

We assign color(n+i+j+ 4)m+n+3to edgev2iv1j,

i= 1;2;···;n;j= 1;2;···;m.

We construct a cycleCsuch that vertex set ofCism+

n+ 3colors{1;2;···;m+n+ 3}and edge set ofCis i)m+n+3(i+ 1)m+n+3|i= 1;2;···;m+n+ 3}.

The color setS(v51)contains justm+n+ 2colors from

(1) m +n+3to(m+n+ 2)m+n+3along cycleC.

The color setS(v41)contains justm+n+2colors which

are divided into two parts, the first part is{1}, the second part is from(3)m+n+3to(m+n+ 3)m+n+3along cycleC.The color setS(v31)contains justm+n+2colors which are divided into two parts, one part is from 2 to 3 along cycle

C, other part is from(5)m+n+3to(m+n+ 4)m+n+3along

cycleC. The color setS(v2i)contains justm+ 3colors which are divided into two parts, one part is from(i+2)m+n+3to(i+ 4) m +n+3along cycleC, other part is from(n+i+5)m+n+3 to(m+n+i+ 4)m+n+3along cycleC,i= 1;2;···;n. The color setS(v1i)contains justn+3colors from(n+i+ 2) m +n+3to(2n+i+4)m+n+3along cycleC,i= 1;2;···;m.

From the above discussions we can see that:

1. The number of the colors in each color setC(x)is equal

to the degree of vertexx;

2. The color sets of any two adjacent vertices with the same

degree are different. Thus the resulting coloring is a(m+n+ 3)-AVDPEC of K m;n;1;1;1. The proof is completed.

Theorem 2.5Ifm > n > p >1, then′

a(Km;n;p;1;1) = m+n+p+ 2. ProofObviously we have∆(Km;n;p;1;1) =m+n+p+1.

By Lemma 1.3,′

a(Km;n;p;1;1)>∆(Km;n;p;1;1) + 1 =m+ n+p+2:In order to prove′a(Km;n;p;1;1) =m+n+p+2, we need only to give the(m+n+p+2)-AVDPEC ofKm;n;p;1;1.quotesdbs_dbs14.pdfusesText_20