L(p,q)-labeling Of Some Special Kinds Of Graphs

A graph G is a an ordered triple, consisting of a nonempty set V(G) of vertices, a set E(G) of edges, and an incidence functionψ_G that associates with each edge of G an unordered pair of vertices of G.The square graph of G is G²: G² has the same vertices set with G, and any two vertices in G² is adjacent if and only if the two vertices' distance in G is at most 2.Graphs in this paper are finite, non-loop and non-mutiple edges. The vertex colouring of a graph: if vertices of G can be divided into k sets : V₁,V₂,…,V_k, and every V_i is independent, that means no adjacent vertices in the same set. Then we call G is k-colourable . The minimum k is called the chromatic number of G, denoted asχ(G).L(p.q)-labeling of a graph G is : for integers p≥0, q≥0, if exists a mapping L:V(G)→{0,…,k}, satisfied that for any two vertices u,v in G:·| L(u)-L(v)|≥p, if dist(u, v) = 1·| L(u)-L(v)|≥q, if dist(u,v)=1Then we call it a L(p, q)-labeling of G. To the minimum k, denoted asλ_q^p(G).A Path P_n is such a graph: its vertices set is V(P_n)={v₁,v₂,…,v_n}, its edges set is E(P_n) ={v₁v₂,v₂v₃,…,v_n-1v_n}, and the vertices v₁ v_n are called the endpoints of P_n. We usually denote P_n as v₁,v₂,…,v_n. A cycleG_n is such a graph: its vertices set is V(C_n)={v₁,v₂,…,v_n}, its edges set is E(C_n) = {v₁v₂,v₂v₃,…,v_n-1v_n,v_nv₁}. So a cycle has no endpoints. We call C_n a odd cycle, if and only if n is odd; We call C_n a even cycle, if and only if n is even. A complete graph K_n is consisting of n vertices, and any two vertices are adjacent.Cartesian product graphs: for graph G and H, let V(G)={u₁,u₂,…,u_m} and V(H)={v₁,v₂,…,v_n}. The Cartesian product graph G×H defined: V(G×H)=Planar graphs definition: if a graph G can be drawn in the plane so that its edges intersect only at their ends.We get the conclusion: For any graph G and its square graph G², we have the result :And corollaries from this conclusion:For any path P_m and P_n(m≥3,n≥3), the Cartesian product graph P_m×P_n, we have the result:For any cycle C_m and path P_n(m≥3,n≥3), the Cartesian product graph C_m×P_n, we have the result:For any complete graph K_m and path P_n(m≥3,n≥3), the Cartesian product graph K_m×P_n, we have the result:For any complete graph K_m and cycle C_n(m≥3,n≥3), the Cartesian product graph K_m×C_n, we have the result: For any cycle C_m and G_n(m≥3,m≠5,n≥3), the Cartesian product graph C_m×C_n, we have the result:For any planar graph G, we have the result:...