Applied Mathematics, 2010, 1, 366-369
doi:10.4236/am.2010.15048 Published Online November 2010 (http://www.SciRP.org/journal/am)
The (2,1)-Total Labeling of mn PS 
1 and mn PS  1
Sumei Zhang, Qiaoling Ma, Jihui Wang
School of Science, University of Jinan, Jinan, China
Received June 14, 2010; revised September 3, 2010; accepted August 7, 2010
Abstract
The (2,1)-total labeling number 2()
TG
 of a graph G is the width of the smallest range of integers that
suffices to label the vertices and the edges of G such that no two adjacent vertices have the same label, no
two adjacent edges have the same label and the difference between the labels of a vertex and its incident
edges is at least 2. In this paper, we studied the upper bound of 2()
TG
 of 1nm
SP
 and 1nm
SP
.
Keywords: Total Labeling, Join of Graph, Path Graph
1. Introduction
Our terminology and notation will be standard. The
reader is referred to [1] for the undefined terms. For a
graph G, let )(GV , )(GE , )(ΔG and )(Gδ denote,
respectively, its vertex set, edge set, maximum degree
and minimum degree. We use )(vN to denote the
neighborhood of v and let )()( vNvd G
 be the de-
gree of v in G. Let ),( yxd denotes the distance of
vertices y
x
, of G,

x is the smallest integer greater
than
x
.
Motivated by the Frequency Channel assignment
problem. Griggs and Yeh [2] introduced the )1,2(L-
labeling of graphs. This notion was subsequently ex-
tended to a general form, named as ),( qpL -labeling of
graphs. Let
p
and q be two nonnegative integers.
An (,)
L
pq -labeling of graph G is a function f
from its vertex set )(GV to the set
 k,2,1,0 for
some positive integer k such that pyfxf  )()(
if
x
and yare adjacent, and qyfxf  )()( if
x
and
y are at distance 2. The ),( qpL -labeling number
)(
,Gλqp of G is the smallest k such that G has an
),( qpL -labeling f with max  kGVvvf )(|)( .
Whittlesey et al. [3] investigated the )1,2(L-labeling
of incidence graphs. The incidence graph of a graph
G is the graph obtained from G by replacing each
edge by a path of length 2. The )1,2(L-labeling of the
incidence graph of G is equivalent to an assignment
of integers to each element of )()(GEGV  such that
adjacent vertices have different labels, adjacent edges
have different labels, and incident vertex and edge
have the difference of labels by at least 2. This labeling
is called )1,2(-total labeling of graphs, which was in-
troduced by Havet and Yu [4], and generalized to
)1,( d-total labeling form. Let 1d be an integer. A
)1,( dk

-total labeling of graphG is an integer-valued
function f defined on the set )()( GEGV  such
that






. edge oincident t vertex if,
adjacent; are and edges if,1
adjacent; are and verticesif,1
)()(
yxd
yx
yx
yfxf
The )1,( d-total labeling number, denoted )(GλT
d, is
the least integer k such thatG has a )1,( dk -total
labeling.
When 1

d, the )1,1( -total labeling is the well-
known total coloring of graphs, which has been inten-
sively studied [5-7].
It was conjectured in [4] that 12Δ)( dGλT
d for
each graph G, which extends the well-known Total
Coloring Conjecture in which 1d. It was also shown
in [4] 1Δ2)(  dGλT
d for any graph G. The(,1)d-
total labeling for some kinds of special graphs have
been studied, e.g., complete graphs [4], outerplanar
graphs for 2

d [8], graphs with a given maximum
average degree [9], etc.
In this paper, we studied the )1,2(-total labeling of
joining graph with star and path1nm SP
, and the car-
tesian product of star and path 1nm SP
. The follow-
ing two lemmas appeared in [4], which are very useful.
This work was supported by the Nature Science Foundation of Shandong
Province (Y2008A20), also was supported by the Scientific Research and
Development Project of Shandong Provincial Education Department
(TJY0706) and the Science and Technology Foundation of University o
f
Jinan (XKY0705).

S. M. ZHANG ET AL. 367
Lemma 1.1. Let G be a graph with maximum de-
gree Δ, then () 1
T
dGd
 .
Lemma 1.2. If () 1
T
dGd
 , then the vertices
with maximum degree of G must be labeled 0 or
1Δ d.
2. The (2,1)-Total Labeling of 
n+1 m
S
P
Let 1
G and 2 G be two graphs, by starting with a dis-
joint union of 1
G and 2 G, adding edges by joining
each vertex of 1
G to each vertex of 2 G, we can obtain
the join of graph 1
G and 2 G, denoted 12 GG.
Let 1n S be a star with n+1 vertices 01 ,, n vv v, in
which 0 ()dv n, we call 0
v the center of 1n
S

. Let
m
P be a path with m vertices 12 ,, m uu u. Then
1nm
GS P

 has following propositions:
1) 0 () ()Gdvmn ;
2) 23 () ()du du1 () 3
m
du n

 
1
()( )2
m
du dun;
3) 12 ()( )()1
n
dv dvdvm .
For 1, 2n, 1n S is a path, S. M. zhang [10] had
studied the )1,2(-total labeling of mn
PP. So in the
sequel, we only consider the case 3n.
Theorem 2.1. Let 1nm GS P

, if 2

nm, then
2() 1
TG
 .
Proof. By lemma 1.1, it’s need to prove
2() 11
TGmn
  .
Now, we give a (1)(2,1)mn -total labeling of
G as follows:
For 1, 2,,in and 1,2,,jm, let
()( 1)mod(1)
ij
fvui jm ,
0
() 1
i
f
vv i, 0 () 1
f
vmn, () 2
i
fv m
0
() (1,2,,1)
j
fvun jjm ,0 ()
m
f
vu n

,
1
() 3,fu n(),
m
f
umn
()2(2,3,,1)
j
fu jjm ,
1
,1 2
() 1, 12
jj
mnjmandjisodd
fuu mnjmandj is even





1
() 2
mm
fuum n
.
It’s easy to see that
f
is a (1)(2,1)mn-total
labeling of 1nm SP
, so we have
2() 11
TGmn
  .
Theorem 2.2. Let 1nm GS P

, if 17mn
then 2() 1
TG
 
Proof. By lemma 1.1, it’s need to prove
2()122
TGn
 .
Now, we give a (22) (2,1)n -total labeling of G
as follows:
For 1,2,,in and 1,2,,1jn, let
()( 1)mod(2)
ij
fvui jn
0
() 1
i
f
vv i,
22, 0,
() 3,1,2,,.
i
ni
fv ni n




0
() (1,2,)
j
f
vunjjn

,01 ()
n
f
vu n


,
1
()1(1,2,,),
jj
f
uujjn



21,1 1
() ,
2, 11
nk
nknandj is odd
fu nknandj is even





Let ()2 2,
n
fu n

1 ()21,
n
fu n
 Since 6n,
we can see that
2
()()22(1)32,
nn
fu fvunnn


()()22( 3)51,
ni
fu fvnnn

.
It’s easy to see thatf is a )1,2()1Δ( -total label-
ing of G for 71


nm .
Theorem 2.3. Let 1nm GS P


, if 614



nm ,
then 2() 2
TG


 .
Proof. Since )32()2Δ(


n, we can also give a
)1,2()32(


n-total labeling of G as follows:
Let 0 () 23fv n

, 1 ()21
n
f
un
, and let
22,01
() ,
21,0 1
nk
nknandj is odd
fu nknandj is even





Then label other edges and vertices of G as the proof
of theorem 2.2.
Obviously,
f
is a )1,2()32( n-total labeling of
G, so we have 2()2
TG


 .
Theorem 2.4. Let 1nm GS P


, if 6nm , then
2
1() 2
Tm
nG
GS P
 

.
Proof. Since )22()2Δ(


n, we can also give a
)1,2()22(


n-total labeling of G as follows:
Let ()( 1)mod(2)(,1,2,,)
ij
f
vuijni jn

 ,
0
() 1
i
f
vv i

, 0 () (1,2,,)
j
f
vunj jn ,
0
() 22fvn

, ()21(1,2,,)
i
f
vni n,
1
()1(1,2,,1)
jj
fuuj jn


 ,
()2(1,2, ,2)
j
fun jjn

 ,
1
()23,
n
fu n


22)(  nufn.
For 6n, it’s easy to see that
131
()( )23(1)42,
nn
fu fvunnn



Then
f
is a )1,2()2Δ(


-total labeling of G, this
prove the theorem.
Theorem 2.5. Let 1nm GS P


, if 5nm, then
2() 1
TG


 .
Proof. For 1, 2,,in

;1,2,,jm, let
()( 1)mod(1)
ij
fvui jn

, and 0 () 1,
j
f
vu j


0
() 1
i
f
vv i

,

S. M. ZHANG ET AL. 368
3, ,
() 4, .
j
njisodd
fu nj is even




1
1, ,
() .
6,
jj
njisodd
fuu nj is even





Let
0
() (1,2,,1),
i
fvvimin 
()(1,2, ,2),
i
fvm nin
0
() 1,fvm n 1 ()2 (),
nn
f
vn fv

0
()
n
f
vv m

Notice that 5 mn , it’s easy to prove that f is a
)1,2()1Δ( -total labeling of G, this prove the theo-
rem.
3. The (2, 1) -Total Labeling of mnPS

1
The cartesian product of graph G and
H
, denoted
HG , which vertex set and edge set are the follows:

()(,)|,VG HuvuGvH,
()EG H

(,)( , )|,( );,().uvu vvvuuEGoruu vvEH
 

Let ,(0,1, ;1,2,,)
ij
wi njm denote the vertex
(,)
ij
vu of the graph 1nm SP
.
Obviously, for 2m,
10,
()1()(1,2)
nm j
SPndwj

 , the degree of
other vertexes is 2. For 3,m
10,
()2()(1,2,,),
nm j
SPn dwjm

 
,1 ,
()( )2(1,2,,),
iim
dw dwin the degree of other
vertexes are 3.
For 1, 2,n 1n Sis a path, S. M. zhang [11] had
studied the )1,2( -total labeling of mn PP. So in the
sequel, we only consider the case 3n.
Theorem 3.1. Let 1nm GSP

, then 2() 1
TG


 .
Proof. By lemma 1.1, it’s need to prove 1Δ)(
2Gλ
T.
Case 1. If ,4,2  nm then 1Δ n.
We give a )1,2()2(n-total labeling of G as fol-
lows:
By lemma 1.2, we let ,2)(,0)( 2,01,0 nwfwf
0, ,
1,1, 2,,;1, 2
2
2,1,2,,2;1,2
22
()2, 1,;1,
01;2
1;2.
jij
n
ii j
nn
ii nj
fw wiinnj
in j
inj





 
 
 
 


 










1,1 1,2
()5,()0,fw fw
1,1 1,2
()3;fww 
2,12,2
()1,()0,fw fw
2,12,2
()4;fw w
,1,2
()1,()2(3,4, 1),
ii
fw fw in

 
,1 ,2
()1,()3
nn
fw fw

,
,1 ,2
()2(0, 3, 4,).
2
ii
n
f
wwi n



 
For 4n, we have
0,20,10,2
()() 2(2)2,
22
nn
fwfwwnn
 


 

then fis a )1,2()2(


n-total labeling of G for
2m

, 4n.
The )1,2(5

-total label of 42 SP as follows:
Let ,5)(,0)( 2,01,0  wfwf 1,1 1,2 ()2,()3;fw fw
2,12,2
()5,()0,fw fw

3,1 3,2 ()1,()2;fw fw
0,10,2
()3,fww

1,1 1,2
()5,fww 2,1 2,2 ()3,fww

3,13,2
()4;fww

0,11,1
()4,fw w0,2 1,2 ()1,fww

0,13,1
()5,fww

0,2 3,2
()0;fw w
0,12,10,22,2
()()2.fw wfww


Case 2. If ,4,3nm then 2Δ n.
We can also give a )1,2()3(

n-total labeling of G
as follows:
For mj


1, let 0,
3, ,
()0,.
j
nj is even
fw jisodd




0, ,
1,1,2,;1,2,,
2
3,1,2,2;1,2,
22
()3, 1,;,
0, 1;,
1, ;.
jij
n
iij m
nn
iinjm
fwwiinnandj is odd
inandj is even
inandj is even

 



 
 
 
 


 










1,
4, ,
() 5, .
j
jisodd
fw j is even


, 2,
5, ,
()6,.
j
jisodd
fw j is even



For 11jm

,
let ,,1
0,1, 2;,
()
1,1, 2;.
ijij
iandj is odd
fw wiandj is even





For 1jm

,
let ,
1,3, 41;,
()2,3,41;.
ij
inandj is odd
fw inandj is even






,
1, ,
()3, .
nj
jisodd
fw j is even



For 11jm

,

S. M. ZHANG ET AL. 369
,,1
2,0,3,4;,
2
()
3,0, 3,4;.
2
ijij
ninandj is odd
fw wninandj is even




 







If mjn  1,4 and
j
is even, we can see that
0,0,0, 1
()()3(3)2,
2
jjj
n
fwfwwn





0, 2,
()() 361,
jj
fwfw n
then fis a (3)(2,1)n -total labeling of 1nm SP


.
Case 3. If 3,mn then 5.
We give a )1,2(6-total labeling of 4m SP as fol-
lows:
)2,1(4)( ,1,0 mjwwf jj  ,
For mj1, let 0,
0, ,
()6,.
j
jisodd
fw j is even



0, 2,
5, ,
()
0, .
jj
jisodd
fw wj is even



0, 3,
6, ,
()
1, .
jj
jisodd
fw wj is even



,
1,1, 2;,
()2,1,2;.
ij
iandj is odd
fw iandj is even




3,
2, ,
()3, .
j
jisodd
fw j is even



For 11jm,
let 0,0, 1
2, ,
()
3, .
jj
jisodd
fw wjis even




1,1, 1
5, ,
()
6, .
jj
jisodd
fw wjiseven




2,2, 1
4, ,
()
6, .
jj
jisodd
fw wj is even




3,3,1
0, ,
()
5, .
jj
j is odd
fw wj is even



.
It is easy to see that 21
()1
T
nm
SP 

. This prove
the Theorem.
4. References
[1] J. A. Bondy and U. S. R. Murty, “Graph Theory with
Applications,” MacMillan, London, 1976.
[2] J. R. Griggs and R. K. Yeh, “Labeling Graphs with a
Condition at Distance 2,” SIAM Journal on Discrete
Mathematics, Vol. 5, No. 1, 1992, pp. 586-595.
[3] M. A. Whittlesey, J. P. Georges and D. W. Mauro, “On
the λ-Number of n Q and Related Graphs,” IAM
Journal on Discrete Mathematics, Vol. 8, No. 1, 1995, pp.
499-506.
[4] F. Havet and M. Yu, “)1,( d-Total Labeling of Graph,
Technical Report 4650,” INRIA, Sophia Antipolis, 2002.
[5] O. V. Borodin, A. V. Kostochka and D. R. Woodall, “List
Edge and List Total Coloring of Multigraphs,” Journal of
Combinatorial Theory, Series B, Vol. 71, 1997, pp. 184-
204.
[6] M. Molloy and B. Reed, “A Bound on the Total Chro-
matic Number,” Combinatorics, Vol. 18, No. 2, 1998, pp.
241-280.
[7] W. F. Wang, “Total Chromatic Number of Planar Graphs
with Maximum Degree Ten,” Journal of Graph Theory,
Vol. 54, No. 1, 2007, pp. 91-102.
[8] D. Chen and W. F. Wang, “)1,2(-Total Labeling of
Outerplanar Graphs,” Discrete Applied Mathematics, Vol.
155, No. 18, 2007, pp. 2585-2593.
[9] M. Montassier and A. Raspaud, “)1,(d-Total Labeling of
Graphs with a Given Maximum Average Degree,”
Journal of Graph Theory, Vol. 51, 2006, pp. 93-109.
[10] S. M. Zhang and K. Pan, “The)1,2(-Total Labeling of
nm PP,” Journal of University of Jinan, Vol. 23, No. 3,
2009, pp. 308-311.
[11] S. M. Zhang and Q. L. Ma, “The (,1)d-Total Labeling
of nm CP

,” Journal of Shandong University (Nature
Science), Vol. 42, No. 3, 2009, pp. 39-43.