L(2, 1)-labeling Of 3-regular Graphs With Perfect Matching And The Optimal Labeling Of Caterpillar

The labeling problem is the extension of the graph coloring problem, And there are extensive applications in the true life.In this thesis, we will discuss two kinds of graph coloring problems: L(2,1 )-labeling and optimal label. Given a graph G, a L(2, 1)-labeling of G is a function f: V(G) → {0,1,2, …} such that:Where d_G(u, v), the distance of u and v, is the lengthen of a shortest path between u and v. A k — L(2,1)-labeling is a L(2, 1)-labeling such that no label is greater than k. The L(2,1)-labeling number, denoted by λ(G), is the minimum k such that G has a k - L(2, 1)-labeling. The problem of labeling a graph with a condition at distance two was first investigated by Griggs and yeh. They considered the relationship between A(G) and invariants X(G), Δ(G) and | V{G) |. They show that A(G) ≤ Δ²(G) + 2Δ(G) and conjectured that λ(G) ≤ Δ²(G) for Δ(G) ≥ 2. In this paper, we define a matched sum of graphs, and obtain bounds on its λ-number. We apply these results to a special 3-regular graph of matched sums, and show that these 3-regular graphs have λ-numbers which are at most 9, consistent with the conjecture of Griggs and Yeh. We next show that, excluding the Peterson graph, the λ-numbers of these 3-regular graphs are at most 8 otherwise. We conjecture that there are no 3-regular graphs with λ-number 8.A labeled graph is an ordered pair (G, L) consisting of a graph G and its labeling L : V(G)→ {1,2, …,n}, where n = |V(G)|. An increasing nonconsecutive path in a labeled graph (G, L) is either a path {u₁, u₂,…, u_k) (k ≥ 2) in G such that L(u_i,) + 2 ≤ L(u_i+1 for all i = 1,2, ...,k - 1 or a path of order 1. The total number of increasing nonconsecutive paths in (G, L) is denoted by d(G, L). A labeling L is optimal if the labeling L produce the largest d(G, L).ln this paper, we give an optimal labeling to caterpillar graph.An interesting conjecture on this topic was raised by Griggs and Yeh . They conjectured that λ(G) ≤ Δ² for any graph G with maximum degree Δ ≥2. This conjecture stimulated a lot the study of λ-number, and it was proved by to be true for quite a few classes of graphs. For general graph, Griggs and Yeh first show that λ(G) ≤ Δ² + 2Δ. Then Chang and Kuo improved that λ(G) ≤ Δ² + Δ. Then D.Kr (?) 1 and R.Skrekovski improved that Δ² + Δ - 1.In this paper, we will show the following theorem and prove it: If the complement G^c of G has no hamilton path and Δ ≥2, then A(G) < Δ²; Moreover, if Griggs and Yeh's conjecture isn't true for some graph G with Δ ≥ 2, then λ(G) ≤ n-2, where n - |V(G)|. (If λ(G) ≥n-1, Δ ≥ 2, then λ(G) ≤ Δ².)...