The Adjacent Vertex Distingushing Edge-coloring And Total-coloring Of Lexicographic Product Graphs And Its Mycielski’ Graphs

Let G be a simple graph with vertex set V(G) and edge set E(G). An edge-coloringσ of G is called an adjacent vertex distinguishing edge-coloring of G if Sσ(u)≠Sσ(v) for any uv∈E(G), where Sσ(u) denotes the set of colors of edges incident with u. A total-coloring σ of G is called an adjacent vertex distinguishing total-coloring of G if Fσ (u)≠Fσ (v) for any uv∈E(G), where Fσ(u) denotes the set of colors of edges incident with u together with the color assigned to u. The minimum number of colors required for an adjacent vertex distinguishing edge-coloring (resp. an adjacent vertex distinguishing total-coloring) of G is denoted by χ’as(G)(resp. χat(G)).Firstly, we constructed two classes of graphs Φn and Δn, where any graph G of Φn has only one vertex of maximum degree and it satisfy the condition χ’as(G)=|V(G)|-1=n-1; any graph G of Γn has only one vertex of maximum degree and it satisfies the condition χar(G)=|V(G)|=n.Secondly, we studied the adjacent vertex distinguishing edge-coloring of Lexicographic Product Graph G[H]and its Mycielski’ Graph M(G[H]), where G is any graph of Φn and H is a simple graph of order m. We get the following results.(1) If H is a connected graph, then χ’as(G[H])≤(n-1)m+min{χ’(H)+1,χ’as(H)}, where χ’(H) denotes the edge chromatic number of H.(2) If H is a connected graph and there exists an k-adjacent-vertex distinguishing-edge coloring of G[H], then χ’as(M(G[H]))≤k＋Δ(G[H]).(3) If H is the complement of a complete graph, or H is a tree and there no two vertice of maximum degree are adjacent in H, then χ’as(G[H])=Δ(G[H]),χ’as(M(G[H]))=Δ(M(G[H])).(4) If H is a complete graph, or H is a conneted graph with two adjacent vertice of maximum degree and it is Class1. then χ’as(G[H])＝Δ(G|H|)+1,χ’as(M(G[H]))＝Δ(M(G[H]))+1. (5)If H∈Φm,thenχ’as(G[H])=χ’as(H[G])=mn-1;χ’as(M(G[H]))=χ’as(M(H[G]))=2mm-2.(6)Suppose that G=Gk[Gk-1[…G3[G2[G1]]…]],where Gi∈Φn,i=1,2,…,k, k≥2.then χ’as(G)=nk-1,χ’as(M(G))=2nk-2.Finally, we studied the adjacent vertex distinguishing edge-coloring of Lexicographic Product Graph G[H]and its Mycielski’ Graph M(G[H]),where G is any graph of Γn and H is a simple graph of order m.We also get the following results.(1)If H is a connected graph,then χat(G[H])≤(n-1)m+min{χT(H)+1,χat(H)}, where χT(H)denotes the total chromatic number of H.(2)If H is a connected graph and there exists an k-adjacent-vertex distinguishing-edge coloring of G[H],then χat(M(G[H]))≤k+Δ(G[H]).(3)If H is the complement of a complete graph,or H is a tree and there no two vertice of maximum degree are adjacent in H,then χat(G(H])=Δ(G[H])+1,χat(M(G[H]))=Δ(M(G[H]))+1.(4)If H is a complete graph,or H is a conneted graph with two adjacent vertice of maximum degree and it satisfies the condition χT(H)=Δ(H)+1,or H is a tree with two adjacent vertice of maximum degree,or H is a cycle, then χat(G[H])=Δ(G[H])+2,χat(M(G[H]))=Δ(M(G[H]))+2.(5)If H∈Γm,.then χat(G[H])=χat(H[G])=mn,χat(M(G[H]))=χat(M(H[G]))=2mn-1.(6)Suppose that G=Gk[Gk-1[…G3[G2[G1]]…]],where Gt∈Γn,i=1,2,…,k. k≥2.Then χat(G)=nk,χat(M(G))=2nk-1.