### L(p, q)

```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