Lablelling Graphs With A Condition On Neighborhood Of Graphs And L (2,1) -labelling Of Graphs

As an active research field in Graph theory, some scholars presented and studied a few coloring problems with different restrictions. In 2006 the conditional coloring of a graph is introduced by Lai Hongjian etc. Graph labelling is a generalization of the coloring problem and the background is the frequency assignment problem. In 1992 Griggs and Yeh defined the L(2,1)－labelling.As another generalization of the labelling problem,in 2008 Sun Lei defined k－L_1,2－labelling.Conditional colorings of graphs is a generalization of classical coloring in thoery and is first posed in [2].For a integer r＞0, a conditional (k,r)-coloring of a graph is a proper k-coloring of the vertices of G such that both of the following hold :(1)if u, v∈V(G) and adjacent vertices in G,then c(u)≠c(v);and(2)for any v∈V(G),|c(N_G(v))|≥min{|N_G(v)|,r}.For a fix number r＞0, the smallest k such that G has a proper (k,r)-coloring is the rth order conditional chromatic number of G, denoted _Xr(G).By the definition of _Xr(G),it follows immediately that _X1(G)＝_X(G).As a variation of frequency assignment problem,in 1992 Griggs and Yeh proposed the L(2,1)－labelling.A L(2,1)－labelling of graph G is denned as a function c from the vertex set V(G) to the set of all nonnegative integers such that |c(u)－c(v)|≥2 if d(u,v)＝land |c(u)－c(v)|≥1 if d(u, v)＝2. A k－L(2,1)－labelling is an L(2,1)－labelling such that no lable is greater than k. The L(2,1)－labelling number of G,denoted byλ(G), is the smallest number k such that G has a k－L(2,1)－labelling .If c is aλ(G)－L(2, 1)－labelling of graph G , then c^-1(i)＝{v∈V(G)|c(v)=i} and the cardinal number of |c^-1(i)| is denoted by c^-1(i). We call the integer h(0＜h＜k),a hole of c if and only if |c^-1(h)|＝0. The hole index of a graph G,denotedρ(G),is the minimum number of holes taken over allλ(G)－L(2,1)－labelling of graph G .A k－L_1,2－labelling of graph G is defined as a function c : V(G)→{0,1,2... k} such that both of the following hold :(1)If uv∈E(G) ,then c(u)≠c(v);and(2)If there is a vertex w such that u, v∈N_G(w),then |c(u)－c(v)|≥2.The lablelling numbers with a condition on neighborhood of G,denoted by L_1,2(G), is the smallest number k such that G has a k－L_1,2－labelling .If c is a k－L_1,2－labelling of graph G , then c^-1(i)＝{v∈V(G)|c(v)＝i} and the cardinal number of c^-1(i) is denoted by |c^-1(i)|. We call the integer h(0＜h＜k),a hole of c if and only if |c^-1(h)|＝0.The maximum degree of G is denoted byΔ(G),the minimum degree of G is denoted byδ(G),the distance of u, v in graph G is denoted by d(u, v),the neighborhood of v in G is denoted by N_G(v). In the second chapter we have the following theorems:Lemma 2.1.1 For any simple graph G,L_1,2(G)≥2Δ(G)－1.Lemma 2.1.2 If G is a simple graph and L_1,2(G)＝2(Δ(G)－1),then for any vertex v with d(v)＝Δ(G),c(v)≡1(mod2), and for any u∈N_G(v),c(u)＝2i(i＝0,1,2...Δ(G)－1).Theorem 2.1.3 If there are adjacent vertices u, v∈V(G) both with maximum degree,then L_1,2(G)≥2Δ(G)－1.Theorem 2.1.4 If G is a regular graph,Δ≥4 and there exists odd cycle ,then L_1,2(G)≥2Δ(G).Theorem 2.1.5 G is a cycle,if |V(G)|≡0(mod4),L_1,2(G)=3;if not,L_1,2(G)＝4.Theorem 2.1.6 For a k―degenerate graph G with triangle-free,ifΔ(G)≠4,then 2(Δ－1)≤L_1,2(G)≤Δ(6k－3)＋k－3k².Theorem 2.2.1 G is a tree,Δ(G)≥3 and there are adjacent vertices u, v∈V(G) both with maximum degree,then L_1,2(G)＝2Δ(G)－1.Theorem 2.2.3 G is a tree,Δ(G)≥3 and for any two vertices u,v∈V(G) both with maximum degree,d(u, v)≡0(mod2) and d(u, v)≠0,then L_1,2(G)＝2(Δ(G)－1). Theorem 2.2.4 G is a tree,Δ(G)≥4 and there exists a path containing all verteices with maximum degree, if for any two vertices u, v∈V(G) both with maximum degree,d(u, v)≡1(mod2) and d(u,v)≠1,then L_1,2(G)＝2(Δ(G)－1).Theorem 2.2.5 G is a tree and only has a vertex with maximum degree,then L_1,2(G)＝2(Δ(G)－1).In the second chapter we give some properties of G if c is a minimum labelling with a condition on neighborhood of G and h is a hole of c.Property 2.3.1 G is a simple graph,if c is a minimum labelling with a condition on neighborhood of G and h is a hole of c, then h－1 and h＋1 are not the holes of c.Property 2.3.2 G is a simple graph,if c is a minimum labelling with a condition on neighborhood of G and h is a hole of c. If |c^-1(h－1)|≥2 or |c^-1(h＋1)|≥2 and c(u)＝h－1,c(v)＝h＋1,then there must exist a vertex x which satisfies d(u, x)≤2 and c(x)＝h＋1 or a vertex y which satisfies d(v, y)≤2 and c(y)＝h－1.Property 2.3.3 G is a simple graph with triangle-free,c is a minimum labelling with a condition on neighborhood of G and h is a hole of c. If for any lable i satisfies |c^-1(i)|≥2,and c(v)＝h－1 or h＋1,then there exists two vertices v₁,v₂ which satisfy d(v,v₁)＝1,d(v,v₂)＝2,c(v₁)＝c(v₂)＝h＋1 or h－1 and v₂(?)N_G(v₁).Property 2.3.4 G is a simple graph with triangle-free, c is a minimum labelling with a condition on neighborhood of G and h is a hole of c. If there exists a path uv₀v with c(u)＝h－1,c(v)＝h＋1 and for any x which satisfies d(u, x)=2,but c(x)≠h＋1, for any y which satisfies d(v, y)＝2,but c(y)≠h－1, then |c^-1(c(v₀))|＝1.Property 2.3.5 If c is a minimum labelling with a condition on neighborhood of G and h is a hole of c,and |c^-1(h－1)|＝1, |c^-1(h＋1)|≥2.If c(u)＝h－1,then for any v_i with c(v_i)＝h＋1,there exists a path uw_iv_i.If for any v_i which satisfies d(u,v_i)≠1,then |c^-1(c(w_i))|＝1.Or there only exists a vertex v_i which satisfies d(u,v_i)≠1.G is a simple graph,V(G)＝{v₁,v₂,…,v_n},let V(G[I₂])＝{v₁,…,v_n,v₁^',…,v_n^'}, E(G[I₂])＝E(G)∪{v_i^'v_j^',v_i^'v_j|v_iv_j∈E(G)}, then G[I₂] is the splited gragh of G.If G＝(V(G),E(G)),V(G)＝{v₁,v₂,v₃,…v_n}, let V(M(G))＝{v₁,v₂,…v_n,u₁,u₂,…u_n,v}, E(M(G))＝{u_iv|i＝1,2…n}∪{u_iv_j|v_iv_j∈E(G)},then M(G) is the Mycielskian graph of graph G. M(G) plays an important part in the research of criticality of graph coloring.In the third chapter, we discuss the relations of conditional chromatic numbers of gragh and of its splited gragh,Mycielskian graph and the conditional chromatic numbers of some special graphs are presented.Then we have the following theorems:Theorem 3.1.1 The relation of graph G and its splited gragh G[I₂] is as follows,Theorem 3.2.1 If 2Δ(G)≥r＞0 ,then any graph G, _Xr(M(G))≥r＋2.Theorem 3.2.2 The relation of graph G and its Mycielskian graph M(G) is as follows,For positive integers k and m,let G(k, m) be the family of graphs defined by G∈G(k, m) if and only if V(G)＝V₀∪V₁∪...V_m,where |V₀|＝|V₁|＝...|V_m|＝k, the induced subgraph G(V_i) is an empty graph for any 0≤i≤m and the induced subgraph G[V_i∪V_j] is a perfect matching for any 0≤i＜j≤m. In the forth chapter,we study the L(2,1)－labelling of G(k,m) and we have the following theorems:Theorem 4.1 For k≥3, n≥2,if G∈G(k,n＋1) and contains a subgraph H∈G(k, n) withλ(H)＝2n andρ(H)＝n, thenλ(G)＝2(n＋1).Theorem 4.2 For k≥3,if G∈G(k, 2),thenλ(G)＝4 andρ(G)＝0 or 2.Theorem 4.3 If G∈G(3,3),thenλ(G)＝6.Theorem 4.4 If G∈G(4,3),thenλ(G)＝6.