| Graph theory is a science which developed rapidly. In the hundred years, it has constructed a complete theoretical system and its application is very rich. For exam-ple, physics, operations research, computer science, cybernetics, information theory and economic management etc. Using the graph theory, these are available to construct a mathematical model. And graph coloring is one of the chief fields in graph research.The channel assignment problem is generally an application of the communication problems, such as radio transmission and mobile telephone network. As resources are limited and frequency is taking an important role in modern science and technology, therefore, how to use these resources effectively has become an urgent, problem. It re-quires that the transmitted signal or frequency is kept at an acceptable level. So we can reduce the use of cost as much as possible. In the channel assignment problem, we want to avoid interference between the transmission signals. If the two sites are very close, these frequency differ by at least2. If the two sites are close, but not too close, the assigned frequency just be different.Inspired by the problem, Griggs and Yeh[13] introduced the L(2,1)-labeling. In2000, G.J.Chang et. extended it to the L(p. l)-labeling[11]. This label has been studied in some articles, Whittesey ct[16] studied the L(2.1)-labeling of first subdivision of 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)-labeling of,s1(G) corresponds to an assignment, of integers to V(G)∪E{G) such that:(1) For any two adjacent vertices u and v of graph G, we have|f(u)-f(u)|≥1:(2) For any two adjacent edges e and e’ of graph G. we have|f(e)-f(e’)|≥1: (3) For any two incident vertex u and edge e, we have|f(u)-f(e)|≥p.We call such an assignment a (p,1)-totel labeling of G. The span of a (p.1)-total la-beling is the maximum difference beteeen two labels. The minimum span of a (p,1)-total labeling of G is called the (p,1)-total number and denoted by λpT(G). It is a total coloring which conditions are strengthened. That is, the labeling of incident vertex and edge differ by at least p. For the labeling problem, more generally, we consider the L(p. q)-labeling problem.In the channel assignment problem, the following situation occurs: If the received frequency band of some transfer stations are uncontrolled or broken, we can allow some labeling vertices unrestricted. To solve this problem, we can study the improper property of labeling problem. Here, we give the definition of improper labeling.For any vertex u G V(G),we define the k-neighborhood of u as following: Nk(u)={v|d(u,v)=k}. where k=1,2,3.Definition1For positive integers p, q, r, s with p≥q, the improper (r, s, p, q)-labeling of a graph G is an integer assignment L to the vertex set V(G) such that:(1) For each u∈V(G) and v∈N1(u), at most r vertices in N1(u) receive la-bels satisfying:|L(u)-L(v)|<p and for the remaining vertices in N1(u), we have|L(u)-L{v)|≥p.(2) For each u∈V(G) and v∈N2(u), at most s vertices in N2(u) receive la-bels satisfying:|L(u)-L(v)|<q and for the remaining vertices in N2(u), we have|L(u)-L{v)|> q.The span of an improper (r, s,p, q)-labeling is the maximum difference between two labels. The minimum span taken over all improper (r, s,p,q)-labeling of graph G is called the λ(r,s)(G;p, q)-number and denoted by λ(r,s)(G;p,q). Without loss of general-ity, the minimum label of improper (r, s,p, q)-labeling of G is0.If u and v are adjacent, we have|L{u)-L(v)|<p, then v is a bad vertex of u. On the other hand, u is a bad vertex of v.If u and v are distance two apart, we have|L{u)-L(v)|<q, then v is a bad vertex of u. On the other hand, u is a bad vertex of v.If for any two bad vertex u and v. we have L(v)=L(v). Then an improper (r, s,p,q)-number of a graph G obtained by that,we call an improper (r,s,p, q)’-labelling. And such an improper (r,s,p,q)’-labelling number,denoted by λ(r,s)(G;p,q).The labeling problem of first subdivision of graph G corresponds to the total label-ing problem of graph G. So, similarly, we can study the improper total labeling problem and give the definition:For any edge e∈E(G),we define the set of the adjacent edge of e as following: N1(e)={e’|e and e’ are adjacent edge};For any vertex v∈N(G),we define the set of the incident edge of v as following: N01(v)={e|e and v are incident};For any edge e∈E{G),we define the set of the incident vertices of e as following: N01(e)={v|v and e are incident}.Definition2For positive integers p, r, s, t, the improper (r, s, t, p,1)-total labeling of graph G is a mapping f:V{G)∪E(G)→{0,1,2,??? k} such that(1) For each u∈V(G) and v∈N1(u), at most r vertices in N1(u) receive labels sat-isfying: f(u)=f(v) and for the remaining vertices in N1(u), we have|f(u)-f(u)|≥1;(2) For each e∈E(G) and e’∈N1(e), at most s edges in N1(e) receive labels satisfying: f(c)=f(c’) and for the remaining edges, we have|f(e)-e(e’)|≥1;(3) For each vertex v∈V(G) and e∈N10(v). at most t(t≤2) edges in N01(v) receive labels satisfying:|f(v)-f(e)|<p and for the remaining edges, we have|f(v)-f(c)|≥p; For each edge e∈E(G) and v∈N01(e), at most t(t≤2) vertices in N01(e) receive labels satisfying:|f(v)-f(e)|<p and for the remaining vertices, we have|f(v)-f(e)|≥p.The span of an improper (r, s, t,p,1)-total labeling is the maximum difference be-tween two labels. The minimum span taken over all improper (r,s,l,p,1)-total labeling of graph G is called the λ(r,s,t)T (G;p,1).If u and v are adjacent, we have f(u)=f(v). Then we c:all u and v arc: a pair of bad vertices.If c and e’ are incident, we have f(e)=f(e’). Then we call e and e’ are a pair of bad edgesIf v and e are incident, we have|f(v)-f(e)|<p. Then we call v and e are a pair of bad vertex and bad edge. Sepecially, for any incident vertex v and edge e, if they are a pair of bad vertex and bad edge, we have f(v)=f(e). Then an improper (r,s, t,p,1)-total labeling number of graph G obtained by that, we call an improper (r,s,t,p,1)’-total labeling. And such an improper (r, s,t,p,1)’-total labeling number, denoted by λ(r,s,t)T (G;p,l).In this paper, we have the following results:Theorem2.2.3Suppose p. q. r are positive integers with p≥q, let G be an outer-planar graph with maximum degree A, then λ(r,1)(G;p,q)≤λ(r,1)(G;p,q)≤(2q-1)(Δ-r)+2(2p-l).Theorem2.3.3Suppose p, q, r are positive integers with p≥q, let G be a Halin graph with maximum degree A, then λ(r,1)(G;p,q)≤λ(r,1)(G;p,q)≤(2q-1)(Δ-r)+6p-4q-1.Definition2.4.l[14] If G is a plane graphs with maximum degree, we have Δ(G)=|V(G)|-k,k=1,2,.... Then we call graph G a hk-graph. If k=1,2, then we call such hk-graph be high maximum degree plane graph.Theorem2.4.5Suppose p,q,r are positive integers with p> q, let G be a h1—graph with|V(G)|≥2, then λ(r,0)(G;p,q)<λ(r,0)(G;p, q)≤(2q-1)(Δ(G)-r)+6p-6q.Theorem2.4.15Suppose p,q,r are positive integers with p≥q, let G be a h2-graph with|V(G)|≥9, then λ(r,0)(G;p,q)≤λ(r,0)(G;p,?)≤(2q-1)(Δ(G)-r)+8p-6q-1.Conjecture Let p.q.r are positive integers with p≥q. then for any graph G. λ(r,s)(G;p.q)=λ(r,s)(G;p,q).Difinition3.1.21[5,22,23] Given two graphs G and H. the cartesian product G□H is denfied as following:V(G□H)=V{G)×V(H),E(G□H)={{u,v)(u’,v’)\v=v1and uu’∈E[G) or u=u’ and uv’∈E(H)}.Theorem3.2.3Pm is a path of length m, V(Pm)={u1,u2,… um, um+1}. H sat-isfies:|H|=n,V(H)={u1,u2,…un},the (p,1)-total number of H is λpT(H), and existing a vertex v such that: there exists at least one edge incident with v whose la-bel is more then the label of v, and the maximum label of the edges incident with v is p+α(α≥0). We consturet the cartesian product Pm□H of Pm and H, V(PmDH)={(ui,uj)|i=1,2,…m,+1;j=1,2,… n}, thenDifinition3.1.3[29] G is a simple graph, V(G)={v1,v2,…vn},we join a m(m≥3) cycle with Vj0∈G(j0∈{1,2,???n}),the new graph is denoted by Cm·G{vjo), simply by G*. G,(i=1,2,···m) are the copies of G, the vertex set and edge set of the new graph G*as following: V(C*)=∪i=1m V(Gi)={vij=l,2,···m;j=1,2,···n};E(C*)=∪i=1m E(Gi)∪{vijo v(i+1)jo|i=1,2,···m-1;jo∈{1,2,??? n}}∪{vmjo v1jo}.Theorem3.2.5The maximum degree of G is Δ(G), and λpT(G)=Δ(G)+p-1. We choose the vertex of any maximum degree as v1. The new graph of definition3.1.3is denoted by Cm·G(v1), simply by G1*, then λ(2,2,0)T (G*1;p,1)≤Δ(G1*)+p-2.Theorem3.2.9Suppose Cn is a cycle of length n, then λ(2,2,0)T(Cn;p,1)=p.Difinition3.1.4[4] Cn is a cycle, suppose V(Cn)={v1,v2···v7l}, we denoted a copy of V(Cn) as {u1,u2,··· un}.we define the vertex set and edge set of new graph Sm as following: V(Sn)={v1,v2···vn.u1,u2,···un};E(Sm)=E{Cn)∪{uiui|i1,2,···n}∪{unv1,u1v2,??? un-1vn}.Theorem3.2.105" is said a.s we just defined in definition3.1.4. then λ(2,2,0)T(Sn; p,1)= p+1.Difinition3.1.5[4] For graph G=(V,E). we call μ(G) be the Mycielsk graph of G,V(μ(G))=V(G)∪{v’|v∈V(G)}∪{w} and w(?) V(G);E(μ(G))=E(G)∪{uv’|u G\/(G),u’∈V’ and uv∈E(G)}∪{wu’|u’∈V’}, where w(?)V(G),V={v’\v G V(G)}.Theorem3.2.11μ(Cn) is said as we just defined in definition3.1.5, then λ(2,2,0)T (μ(Cn);p,1)≤p+[Δ/3]+1, where Δ=Δ(μ(Cn)). |
