Report

L(p, q)-labelings of subdivision of graphs Meng-Hsuan Tsai 蔡孟璇 指導教授：郭大衛教授 國立東華大學 應用數學系碩士班 Outline: • Introduction • Main result • 3 = Δ + 1 with Δ ≥ 4 • Δ ≥ 5, ℎ() ≥ 3 ⟹ ℎ =Δ+1 • Δ ≥ 4, ℎ() ≥ 4 ⟹ ℎ =Δ+1 • Reference Introduction Definition: • L(p,q)-labeling of G： , = 1 ⇒ − () ≥ ∀, ∈ () , = 2 ⇒ − () ≥ • A k-L(p,q)-labeling is an L(p,q)-labeling such that no label is greater than k. • The L(p,q)-labeling number of G, denoted by , (), is the smallest number k such that G has a k-L(p,q)labeling. • = 2,1 (). Example: • L(2,1)-labeling of 4 ： 0 2 0 3 6 4 4 1 6-L(2,1)-labeling 4-L(2,1)-labeling =4 Griggs and Yeh (1992) • They showed that the L(2,1)-labeling problem is NP-complete for general graphs and proved that ≤ ∆2 + 2∆(). • They conjectured that ≤ Δ for any graph G with ∆() ≥ 2. Gonçalves (2005) • ≤ ∆2 + ∆ − 2 with ∆() ≥ 2. Georges and Mauro (1995) • They studied the L(2,1)-labeling of the incident graph G, which is the graph obtained from G by replacing each edge by a path of length 2. • Example： C3 Definition: • Given a graph G and a function ℎ from () to ℕ, the ℎ − of G, denoted by (ℎ) , is the graph obtained from G by replacing each edge in G with a 1 2 −1 path : ( )ℎ ( )ℎ … ( )ℎ , where = ℎ(). • If ℎ = for all ∈ (), we use () to replace (ℎ) . • Example : = 4 (3) (5) Lü • Lü studied the 2,1 − of () and conjectured that 3 ≤ ∆ + 2 for and graph with maximum degree ∆. Karst • Karst et al. studied the , 1 − of () and gave upper bound for (where ≥ 3). • Karst et al. showed that ∆ 2 3 ≤+ ∆ 2 + , − 1 for any graph G with ∆() ≥ 3. From this, we have 3 ≤ ∆ + 2 for all graph G with ∆≥ 3 and = Δ + 1 with Δ() is even and Δ() ≠ 2. Extend , − of subdivisions of graphs. • 3 = Δ + 1 for any graph G with Δ() ≥ 4. • ℎ =∆+1 if ∆() ≥ 5 and ℎ is a function from () to ℕ so that ℎ ≥ 3 for all ∈ (), or if ∆() ≥ 4 and ℎ is a function from () to ℕ so that ℎ ≥ 4 for all ∈ (). , − of (3) for ∆() ≤ 2 Georges and Mauro • They studied the L(p,q)-labeling numbers of paths and cycles and gave the following results. Theorem 1: • For all ≥ 1, , = 1, 0, = 2, , = 3 4, = + , + 2, ≥ 5 ≥ 2, 2, ≥ 5 ≤ 2. Theorem 2: • For all ≥ 3, if ≥ 2, then , , 2, ≡ 0 4 , + 2, = 2, ≡ 2 4 ≤ 3, + 3, ≡ 2 4 ≥ 3. • If ≤ 2, then , 2, ≡ 0 3 , 4, = = 5, + 2, ℎ. Theorem 3: • If ∆() ≤ 2, then , 3 + , Δ = 1 + 2, ≥ 2 ∈ = + 3, ≥ 3 ∈ ℬ 2, ℎ, where = : ℎ ℎ 4 ℬ = : , ≡ 2 ( 4) . 2,1 − of (3) Definition: • An , − of (ℎ) is said to be if = 0 for all ∈ (). • The ℎ of in G, denoted (), is defined by = : ∈ () . • If is a − 2,1 − of (3) and ∈ , then we use () to denoted the set 2,3,4, … − : ∈ 3 () . • An 2,1 − of (ℎ) is said to be a − of (ℎ) if is and ℎ = ∆ + 1. Definition: • Let be an , − of G. For ∈ (), a trail = 1 2 … in (3) is called − , ; , − in (3) corresponding to if • = 0 ≡ 1 ( 3) = ≡ 2 ( 6) = ≡ 3 ( 6) = ≡ 5 ( 6) = ≡ 0 ( 6) 0 0 a c 0 bd Theorem 4: • If G is a graph with ∆() ≥ 4, then pf： 3 = Δ + 1. ∗ ( ∗ ) is minimum Theorem 4: • If G is a graph with ∆() ≥ 4, then pf： 3 = Δ + 1. Theorem 4: • If G is a graph with ∆() ≥ 4, then 3 = Δ + 1. pf： • Case 1: For any − of (3) , 2 ∉ () ∩ () and ∆ + 1 ∉ () ∩ (). Lemma 1: : = 1 2 … − ∆ − 1, ∆ + 1; ∆ − 1, ∆ + 1 − Δ+1 Δ−1 Δ−1 Δ+1 Δ+1 Δ−1 Δ−1 Δ+1 Δ+1 Δ+1 Δ−1 Δ−1 Δ+1 Δ−1 Δ+1 Δ+1 Δ−1 Δ−1 Δ+1 Δ−1 Δ−1 a ∵ Δ + 1 ∈ ( ) Δ+1 ∵ 必定 ≤ ∆ − 3 Theorem 4: • If G is a graph with ∆() ≥ 4, then 3 = Δ + 1. pf： • Case 1: For any − of (3) , 2 ∉ () ∩ () and ∆ + 1 ∉ () ∩ (). • Suppose ∆ + 1 ∈ () ∩ () ∆+1 ∆+1 ∆−1 ∆+1 ∆−1 ∆+1 ∆−1 ∆+1 Theorem 4: • If G is a graph with ∆() ≥ 4, then 3 = Δ + 1. pf： • Case 1: For any − of (3) , 2 ∉ () ∩ () and ∆ + 1 ∉ () ∩ (). • (pf):Suppose ∆ + 1 ∈ () ∩ () ∆+1 ∆+1 ∆−1 ∆+1 ∆−1 ∆+1 ∆−1 ∆+1 Theorem 4: • If G is a graph with ∆() ≥ 4, then 3 = Δ + 1. pf： • Case 1: For any − of (3) , 2 ∉ () ∩ () and ∆ + 1 ∉ () ∩ (). • (pf):Suppose ∆ + 1 ∈ () ∩ () ∆+1 ∆−1 ∆+1 ∆−1 ∆+1 ∆−1 ∆+1 ∆−1 Theorem 4: • If G is a graph with ∆() ≥ 4, then 3 = Δ + 1. pf： • Case 2: • If there exists a − of (3) , such that = = 3 , then there exists a − ′ of (3) , such that 2 ∈ ′ and 3 ∈ ′ . Lemma 2: : = 1 2 … − − 2, ; + 1, − 1 − for some 4 ≤ ≤ ∆ −1 −2 +1 −2 +1 −1 +1 −2 −2 +1 −1 −2 +1 +1 −1 −1 −1 −1 −2 +1 ∵ + 1 ∈ ( ) −2 ∵ − 2 ∈ ( ) Lemma 2: : = 1 2 … − − 2, ; + 1, − 1 − for some 4 ≤ ≤ ∆ −1 −2 +1 −2 −1 +1 −1 −2 −1 +1 −2 −2 +1 −1 −1 −2 +1 ∵ ( − 1) − ≥ 2, ∉ − 2, − 1, +1 ∵ − ≥ 2, ∉ − 1, , + 1 Theorem 4: • If G is a graph with ∆() ≥ 4, then 3 = Δ + 1. pf： • Case 2: • If there exists a − of (3) , such that = = 3 , then there exists a − ′ of (3) , such that 2 ∈ ′ and 3 ∈ ′ . 3 3 2 4 5 3 2 4 2 3 5 4 2 3 5 Theorem 4: • If G is a graph with ∆() ≥ 4, then 3 = Δ + 1. pf： • Case 3: • If there exists a − of (3) , such that 2 ∈ ()(. Δ + 1 ∈ ) and 3 ∈ ()(. Δ ∈ ) ,then there exists a − ′ of (3) , such that 4∈ ′ (. Δ − 1 ∈ ′ ) and 3 ∈ ′ (. Δ ∈ ′ ). 3 2 3 4 Theorem 4: • If G is a graph with ∆() ≥ 4, then 3 = Δ + 1. pf： • Case 4: • If there exists a − of (3) , such that = = for some , 4 ≤ ≤ ∆, then there exists a − ′ of (3) , such that ∪ = , + 1 . +1 Theorem 4: • If G is a graph with ∆() ≥ 4, then 3 = Δ + 1. pf： +1 -1 -1 +1 +2 -1 +1 Theorem 4: • If G is a graph with ∆() ≥ 4, then 3 = Δ + 1. pf： +1 -1 +2 +1 -1 +2 Example: • 3 = 4 for a graph G with ∆ = 3, but (3) is not − . 0 4 2 1 4 3 3 1 1 3 0 0 2 4 = 4 − for some ∈ (4 ) Theorem 5: • If G is 3-regular, then ((3) )=4 if and only if () can be partitioned into two set 1 and 2 , so that 1 = 2 , and = : ∈ , ∈ 1 , ∈ 2 is a perfect matching in G. • pf： Theorem 5: • If G is 3-regular, then ((3) )=4 if and only if () can be partitioned into two set 1 and 2 , so that 1 = 2 , and = : ∈ , ∈ 1 , ∈ 2 is a perfect matching in G. • pf： 4 2 0 2 4 0 2 4 0 0 4 2 0 4 2 4 0 2 2 0 4 2 0 4 Theorem 5: • If G is 3-regular, then ((3) )=4 if and only if () can be partitioned into two set 1 and 2 , so that 1 = 2 , and = : ∈ , ∈ 1 , ∈ 2 is a perfect matching in G. • pf： 4 2 0 0 2 2 4 4 0 0 2 4 3 3 3 3 1 1 1 1 4 2 4 0 0 2 0 4 2 2 0 4 2,1 − of (ℎ) Definition: • Given a graph G, a spanning subgraph of is a factor of G. • A set of factors 1 2 … of G is called a of G if () can be represented as an edge-disjoint union of factors 1 2 … . Lemma: • Given a graph G with ∆ = ∆, there exist a factorization 1 2 … of G, such that every vertex in each has degree at most 2. Theorem 6: • If G is a graph with ∆() ≥ 5, and ℎ is a function from () → ℕ so that ℎ() ≥ 3 for all ∈ () ,then ℎ = Δ + 1. Theorem 7: • If G is a graph with ∆() ≥ 4, and ℎ is a function from () → ℕ so that ℎ() ≥ 4 for all ∈ () ,then ℎ = Δ + 1. • Example: ∆= 4 Theorem 7: • If G is a graph with ∆() ≥ 4, and ℎ is a function from () → ℕ so that ℎ() ≥ 4 for all ∈ () ,then ℎ = Δ + 1. • Example: ∆= 4 1 2 Theorem 7: • If G is a graph with ∆() ≥ 4, and ℎ is a function from () → ℕ so that ℎ() ≥ 4 for all ∈ () ,then = Δ + 1. ℎ • Example: 0 ∆= 4 2 3 5 1 3 4 2 0 2 5 3 0 2 5 1 3 0 2 5 3 0 Theorem 7: • If G is a graph with ∆() ≥ 4, and ℎ is a function from () → ℕ so that ℎ() ≥ 4 for all ∈ () ,then ℎ = Δ + 1. • Example: 0 ∆= 4 5 4 1 1 4 5 0 0 2 Theorem 7: • If G is a graph with ∆() ≥ 4, and ℎ is a function from () → ℕ so that ℎ() ≥ 4 for all ∈ () ,then = Δ + 1. ℎ • Example: 0 ℎ =∆+1 ∆= 4 2 4 5 3 5 1 1 3 1 5 0 2 5 3 0 4 2 4 2 5 3 0 2 5 3 0 Thanks for your listening!