The Packing Coloring And The (p,1) -Total Labelling Of Graphs

Graph theory is a young but rapidly maturing subject. It is a sort of models which can be applied in various science fields such as computer science, physics, biology, chemistry,strategy etc. And graph coloring is one of the chief fields in graph research.The frequency assignment problem is a general framework focused on point-to-point communication, e.g., in radio or mobile telephone networks. This problem requires the interference of frequencies or frequency channels assigned to transmitters keep at an acceptablelevel, in order to making use of the available frequencies in an efficient way. In this problem, we need to assign radio frequency bands to transmitters. In order to avoid interference, if two stations are too close, the separation of the channels assigned to them has to be at least two; if two stations are close (but not too close), they must receive different channels. Motivated by this problem, Griggs and Yeh[10] introduced L(2, 1)-labelling. G.J.Cahng etc.[11] generalized to the L(p, 1)-labelling of a graph G in 2000, the L(p, 1)-labelling of a graph G is an integer assignment L to the vertex set V(G) such that:This labelling has been studied in several articles. Chordal graph has been studied in [11]. Whittlesey et al.[12] studied L(2,1)-labelling of first subdivision of a graph G. The first subdivision of a graph G is the graph s₁(G) obtained from G by inserting one vertex along each edge of G. An (p,1)—total labelling [13] of G corresponds to an assignment of integers to V(G)∪E(G)such that:Let p is an integer, a k - (p, 1)-total labelling of a graph G is a mapping(1)for any two adjacent vertices u, v of G, having |f(u) - f(v)|≥1; (2)for any two adjacent edges e,e' of G, having |f(e) - f(e')|≥1;(3)for a vertex u and its incident edge e of G, having |f(u) - f(e)|≥p.We call such an assignment a (p, 1) - total labelling of G. It is a total coloring strengthened with an extra condition, the condition is that the minimal label separations between incident vertices and edges are at least p.The span of a (p, 1)-total labelling is the maximum difference between two labels. The (p, 1) - total number of a graph G, denoted byλ_p^T(G), is the minimum span of a (p, 1)-total labelling of G. Note that a (1,1)-total labelling is a total coloring asλ₁^T—χ^T - 1) where =χ^T is the total chromatic number.The following definition is given in [22]:Definition 1^[22] G = (V(G), E(G)), d is a positive integer, X is a subset of V(G), if vertices of X are pairwise at distance more than d, then X is a d-packing. The integer d is called the width of the packing X. Obviously, if X is a d-packing of width d, then X is also a packing of width (d - 1) and a (d - 2) etc..Definition 2^[22] Let G = (V(G),E(G)), the smallest integer k such that V(G)can be partitioned into k packings X_i(i = 1,2,…, k) with pairwise different widths and(?) is called the packing chromatic number of G and it denoted byχ_ρ(G). A(packing) coloring of G sizeχ_ρ(G) will be called aχ_ρ(G) -coloring. Because the objectiveis to minimize k, we can assume that X_i is an i- packing for each i.The packing coloring requires the vertex set V(G) can be partitioned into A: packings X_i(i = 1,2,…, k) with pairwise different widths, that is, vertices of X_i are pairwise at distance more than i. The vertices of X_i use the same color.The packing chromatic number is a special vertex coloring and is studied recently two years. This concept has many applications in frequency assignment, resource placementand biological diversity etc..We briefly summerize our main results as follows:Definition 2.1.1^[26] B = {B₁,B₂,…, B_n} is a family set, we say that the graph X(B) = (V, E) with |X(B)| = n is the intersection graph of B when each vertex v_i correspondsto B_i and two different vertices v_i and v_j are adjacent if and only if (?). Suppose Zⁿ = {1,2,…,n}, its power set Z = {Z₁,Z₂,…,Z_2ⁿ| (?), Z_i (?) Zⁿ}. We consider the (p, 1)-total labelling of the intersection graph X(Z' ) of the family set Z' = Z - (?).Theorem 2.1.1 The intersection graph X(Z') is said as we just definied, thenTheorem 2.1.2 If K_n,m(m＞n≥1) is a complete bipartition graph,â–³> p,(l)when n = 1, m≥2 , thenλ_p^T(K_n,m) = m + p - 1.(2)when n≥2, m＞n, (i) If m - n≥2p - 1, thenλ_p^T(K_n,m) = m + p-1.(ii) If m-n≥p and m-n＜2p-1, thenλ_p^T(K_n,m) = m+p.Lemma2.2.1^[20] If G satisfiesλ₂^T(G) =â–³(G) + 1 and f is a (â–³(G) + 1) -(2, l)-total labelling of G using the label set {0,1,2,…,â–³(G) + 1}, then everyâ–³-vertex v of G has f(v) = 0 or f(v) =â–³(G) + 1. We popularize this lemma to the (p, 1)-total labelling:Lemma 2.2.2 If G satisfiesλ_p^T(G) =â–³(G) + p - 1 and f is a (â–³(G) + p - 1) -(p, 1)-total labelling of G using the label set {0,1,2,…,â–³(G) + p - 1}, then everyâ–³-vertex v of G has f(v) = 0 or f(v) =â–³(G) + p - 1.Theorem 2.2.3△＞p, If graph G has aâ–³-vertex v incident with at least d(v) - p + 1â–³-vertex, and the induced subgraph of theâ–³-vertex is triangle-free, thenλ_p^T(G)≥△+p.Definition 2.2.1 G is a simple graph , V(G) = {v₁,v₂,…,v_n}. We join a m(m≥3) cycle with V_j0∈G(j₀∈{1,2,…, n}), the new graph is denoted by C_m·G(v_j0), simply by G^*. G_i(i = 1,2,…, m) are the copies of G, the vertex set and edge set of thenew graph G^* as following : V(G^*) = (?) V(G_i) = {v_j0|i = 1,2,…, m; j = 1,2,…, n},Theorem 2.2.4 The maximum degree of G isâ–³(G), andλ_p^T(G) =â–³(G) +p - 1. We choose the vertex of any maximum degree as v_j0, denoted by v₁. The new graph of definition 2.2.1 is denoted by C_m·G(v₁), simply by G₁^*. thenTheorem 2.2.5 Suppose G satisfies : The (p,1)-total number of G is 0≤λ_p^T(G)≤2p-1, let f is a (p, 1)- total labelling of G: f : V(G)∪E(G)→[0,1,…,λ_p^T(G)], existing a vertex v₀∈V(G) satisfies f(v₀) = 0, We choose the vertex v₀ as v_j0, denoted by v₁. The new graph of definition 2.2.1 is denoted by C_m·G(v₁), simply by G₂^*. Soppose the maximal label of edges incident with v₁ in G is p + a(l≤a≤λ_p^T(G) - p). m is even ,m is odd,Definition 2.2.2 T is a tree, |V(T)| = m, V(T) = {u₁, u₂,…, u_m}. The degrees of the vertices are equal except for the leaf vertices ,â–³(T) =â–³. Let |G| = n, V(G) = {v₁,v₂,…,v_n}. If the (p, 1)-total number of G isλ_p^T(G), G hasâ–³vertices v₁, v₂,…, v_â–³with the same label a₀(0≤a₀≤λ_p^T(G)) and the labels of all the edges incident with v_i(i = 1,2,…,â–³) are less than the label of v_i.G_i(i = 1,2,…, m) are the copies of G, we replace the u_i(i = 1,2,…,m) with G_i(i = 1,2,…, m). When u_iu_j∈E(T), we join a vertex with the label a₀ of G_i to a vertex with the label a₀ of G_j, and the vertex with the label a₀ of G_i(i = 1,2,…, m) only joins to one vertex with the label a₀ of G_j(j≠i). The other vertices of G don't change. The new graph is denoted by T·G(v₁,v₂,…, v_â–³), simply by G'_T.Obviously, we have more than one G'_T which are not isomorphic. But for every G'_T obtained from definition 2.2.2, the following theorem is hold.Theorem 2.2.6 G'_T is said as we just defined, thenλ_p^T(G)≤λ_p^T(G'_T)≤λ_p^T(G) + 2.We replace theâ–³vertices v₁, v₂,…, v_â–³with the same label of G of definition 2.2.2 with the following condition : for any v_i(i = 1,2,…,â–³), there exists at least one edge whose label is more than the label of v_i, and the maximal label of the edges incident with all v_i(i = 1,2,…,â–³) is p + a(0≤a≤λ_p^T(G) - p).We get the new graph according to the way of definition 2.2.2, the new graph is denoted by T·G(v₁,v₂,…, v_â–³), simply by G" T.Obviously, we have more than one G" T which are not isomorphic. But for every G" T, the following theorem is hold.Theorem 2.2.7 G" T is said as we just defined, thenDefinition 2.3.1^[25,51] Given two graphs G and H, the cartesian product Gâ–¡H is defined as following: V(Gâ–¡H) = V(G)×V(H); E(Gâ–¡H) = {(u,v)(u'v')| v = v'and uu'∈E(G) or u = u' and vv'∈E(H)}.Theorem2.3.1 P_m is a path of length m, V(P_m) = {u₁,u₂,…,u_m,u_m+1}. H satisfies : |H| = n, V(H) = {v₁,v₂,…,v_n}, the (p,1)-total number of H isλ_p^T(H), and existing a vertex v such that: there exists at least one edge incident with v whose label is more than the label of v, and the maximal label of the edges incident with v is p + a(a≥0). We construct the cartesian product P_mâ–¡H of P_m and H, V(P_mâ–¡H) = {(u_i,V_j)| i = 1,2,…,m + 1;j = 1,2,…,n}, thenDefinition 3.1.1^[51] Let G is a simple graph with the vertex set V(G)={v₁,v₂,…,v_n}, I₂ is an independent set of two vertices. Let G[I₂] denote the graph obtained from G by replacing each vertex by the two vertices of the independent set I₂ The vertex set and edge set of G[I₂] are following:V(G[I₂]) = {v₁,v₂,…,v_n,v'₁,v'₂…,v'_n}, E{G[I₂]) = E(G)∪{v'_iv'_j,v'_iv_j|v_iv_j∈E(G)}. G[I₂] is the split graph of G.The packing chromatic numbers of the split graphs of some special graphs were given. We defined a new graph according to W_n , the packing chromatic numbers of the new graph and its split graph were given.Definition 3.2.1^[36] Given m(m≥3) graphs G₀, G₁,…, G_m-1, for i = 0,1,…, m-1, let e_i = v_iv_i+1∈G_i, c_m = c₀c₁…c_m-1 be a cycle of length m, construct a new graph as following:(l)Delete the edges e_i for i = 0,1,…, m - 1.(2)Identify all the v_i into a single vertex and name x.(3)Identify v_i+1 and c_i for i = 0,1,…, m - 1(the addition of i + 1 modulo m). We shall denote the resulting graph by S₁(G₀, e₀, G₁, e₁,…, G_m-1, e_m-1), simply by S₁.If given m(m≥3) graphs G_i = K_ni for i = 1,2,…, m, thenS₁(G₀,e₀,G₁,e₁,…,G_m-1,e_m-1) = S₁(K_n1, e₁, K_n2,e₂,…,K_nm,e_m), simply by S'₂. The vertex x is denoted by v₀, and the vertex identified by v_i+1 and c_i denoted by v₁₁,v₂₁…, v_m1; the other vertices of K_ni corresponding to v_i are denoted by v_i1, v_i2,…, v_i(ni-2), i = 1,2,…,m.Theorem 3.2.1 S'₂ is said as we just defined , thenχ_ρ(S'₂) =(?).