| Now there axe many fields as the development of the graph theory.Coloring problem,which comes from the four-color conjecture,plays an important part.Coloring problem is extensively applied to combinatorial analysis and realistics life. Coloring problem is very active, some interesting results and new fields are obtained.Recently some new coloring problems which play an important role in the frequency assignment problem are proposed,such as the packing coloring and (p, 1)-total labelling of G.Definition 1 Let G = (V(G), E(G)) be a graph,d is a positive integer and X is a bipartite set.If for any u,v∈V(G),there is d(u, v)≥d,then X is called a packing,d is called width of X.a d-packing is a (d - 1)-packing and a (d - 2)-packing etc.Definition 2 Let G = (V(G),E(G)) be a graph,andwhere the packings Xi(i - 1,2,…,k) are diffent widths, and k is the minimum integer of the packings Xi with pairwise different widths,k is called the packing chromatic number of graph G and we denote it with Xp(G).A packing coloring of G of size Xp(G) is called a Xp(G)-coloring . Obviously, the objective is to minimize k,we can assume that Xi is an i-packing for each i.The packing coloring based on the distance between the vertices is a parition of the vertex set. It is very difficult to determine the packing chromatic number if the structure of graph is not determined.And the known conclusions are all about graphs of special structures, such as the packing chromatic number of infinite spuare and the subdivision graph S(Kn) of complete graph Kn the infinite 3-regular tree has packing chromatic number 7.Therefore,in the literature[1],the author suspected that to determine the packing chromatic number of any graph is N P-complete problem.In the frequency of distribution,there will be a case in the following:We need to give a transit point for the allocation of frequency bands(each transit point corresponding to an integer has a frequency band).In order to avoid interference,if the two sites are from very near,then difference between the frequency of their differences is at least 2, then they have different frequencies.Inspired by this question,Griggs and Yeh introduced L(2,1)-labellings.Its natural generalization is L(p,1)-labelling.Definition 3 An L(p,1)-labelling of a graph is an assignment L from the vertex set V(G) to the integer set such that:for any u,v∈V(G)(1) |L(u)-L(v)|≥p,if dG(u,v) = 1;(2)|L(u)-L(v)|≥1,if dG(u,v) = 2.Whittlesey et al.in the literature[7] studied L(2,1)-labellings of first subdivision S1(G) of a graph G.The first subdivision of a graph G is the graph S1(G) obtained from G by inserting one vertex along each edge of G.An L(p,1)-labelling of S1(G) corresponds to an L(p,1)-total labelling of G.Definition 4 A k - (p,1)-total labelling of G is an assignment f from the set V(G)∪E(G) to the integer set {0,1,2,…k},such that:(1)|f(u) - f(v)|≥1 for any two adjacent vertices u,v∈V(G);(2)|f(e) - f(e')|≥1 for any two adjacent edges e,e'∈E(G);(3)|f(u) - f(e)|≥p for incident vertex u∈V(G) and edge e∈E(G). The span of a (p,1)-total labelling is the maximum difference between two labels. The minimum span of a (p,1)-total labelling of G is called the (p,1)-total number and denoted byλpT(G). The triviality lower and upper bounds are given by Fr(?)d(?)ic Havet and Min-Li Yu and the (p,1)-total labelling conjecture:λpT(G)≤Δ(G) + 2p - 1.We briefly summerize our main results as following:Definition 2.1 Let G be a connected graph, with V(G) = {v1,v2,…,vn}. Let G' be a copy of G with V(G') = {v'1,v'2,…,v'n}.A new graph D(G) is defined as following:We call it double graph D(G).Theorem 2.1 Let Pn be a path,then Xp(D(Pn)) = 5.Theorem 2.2 Let Wn be a wheel,then Xp(D(Cn)) = n + 2.Definition 3.1.1 Let G and G' be connected graph, withV(G) = {u1,u2,…,un} and V(G') = {v1,v2,…,vn}Between G and G' we add matching uivi,uivi+1,uivi+2,…,uivi+m,…,uivi+(n-1)(i = 1, 2,…,n;m = 0,1,2,…,n - 1;If i + m > n,i + m is the adder in the sense of mod n).Then there will be a series of graphs:Gn,n(1),Gn,n(2),…,Gn,n(m+1),…,Gn,n(n).We called them weak join of two graphs of G and G'.Obviously,Gn,n(n) = G∨G.Theorem 3.1.1 Let Pn be a path,thenλ2T (Pn,n(m+1)) =Δ+ 2 = m + 5(m =0,1,2…,n-2.n>4).Theorem 3.1.2 Let Cn be a cycle,thenλ2T(Gn,n(m+1))≥Δ+ 2 = m + 5(m = 0,1,2,…,n-1);If n is even,thenλ2T(Gn,n(m+1)) =Δ+ 2 = m+5(m = 0,1,2,…,n-1).Definition 3.2.1 Let G be a simple graph,V(G) = {vi,v2,…,vn}.I2 are two independent set points,G[I2] is a graph that every vertex of G is replaced by I2.The vertex set and the edge set corresponds to the following:then G[I2] is called splited graph of G.Theorem 3.2.1 Let Pn be a path and Pn[I2] be a splited graph of Pn,thenTheorem 3.2.2 Let Cn(n≥3) be a cycle and Cn[I2] be a splited graph of Cn,If n is even,thenλ2T(Cn[I2])=6.Theorem 3.2.3 Let Kn[I2] be a splited graph of complete graph Kn,thenλ2T(Kn[I2])≥2n.Definition 3.3.1 Let T(G) be a total graph of G, its vertex set corresponds to the vertex and edge of graph G.The two vertices of total graph are adjacent if and only if corresponding vertexes or edges of G are adjacent,or the corresponding vertex and edge are incident.LetTheorem 3.3.1 Let Cn be a cycle and T(Cn) be a total graph of Cn,thenλ2T(T(Cn))≥6;If n is even, thenλ2T(T(Cn)) = 6.Theorem 3.3.2 Let Pn be a path and T(Pn) be a total graph of Pn,then Theorem 3.4.1 Let G be a tree withΔ(G) = 3,and all the vertices with maximum degree is on a path,thenλ2T(G)≤5.Let Fm be a fan and its order is m + 1,we denote it with Cn·Fm when n hearts of fan are connected into a circle.Letthen there is a theorem following about (2,1)-total labelling of graph Cn·Fm.Theorem 3.4.2 If n = 0(mod2),thenIn the path Pn,join u to v if and only if d(u, v) = k(u, v∈V(Pn)),then the new graph is called Pnk.Then the (2,1)- total labelling of Pnk is given as follows.Theorem 3.4.3 For graph Pnk,if k > 1,n≥3k + 2,thenλ2T(Pnk) = 6.In the cycle Cn,join u to v if and only if d(u,v) = k(u,v∈V(Cn)),then the new graph is called Cnk.Then the (2,1)- total labelling of some C4m2(m≥1) is given as following. Theorem 3.4.4 For graph C4m2,if m≥1,thenλ2T(C4m2) = 6.For complete graph Kn,u,v∈V(Kn),delete the edge uv and obtain Kn - uv.Theorem 3.4.5 If n is an odd integer and n≥3,thenλ2T(Kn - uv) = n +1.Let V(Cn) ={v1,v2,…,vn} and V'(Cn) be a copy of V(Cn) with V'(Cn) = {u1,u2,…,un}.some new graphs Sn,S1n,M(Cn) are defined and some results of (p,1)- total labelling of them are given as following.Sn is defined as following:V(Sn) = V(Cn)∪V'(Cn),and E(Sn) = E(Cn)∪{ui,vi(i=1,2,…,n)}∪{uivi+1(i= 1,2,…,n-1)unv1}.Theorem 3.5.1 If n is even thenλpT(Sn) =Δ+p = p + 4.For graph Sn(if n is even), joint u1u2,u2u3,…,un-1un,unu1 and obtain S1n.Theorem 3.5.2 If n is even thenλpT(S1n) =Δ+p=p+4.The graph obtained by M-structure is denoted by M(G).If V(G) = {v1,v2,…,vn}, thenTheorem 3.5.3 If n is even then n + p-1=Δ+p-1≤λpT(M(Cn))≤Δ+ p + 2 = n + p + 2.
|
PDF Full Text Request