Paper Menu >>
Journal Menu >>
![]() Applied Mathematics, 2010, 1, 366-369 doi:10.4236/am.2010.15048 Published Online November 2010 (http://www.SciRP.org/journal/am) Copyright © 2010 SciRes. 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 E-mail: ss_maql@ujn.edu.cn 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 1d 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 1d. 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. Copyright © 2010 SciRes. AM 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 du1 () 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 3n. 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 6n, 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 6nm , 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 6n, 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. Copyright © 2010 SciRes. AM 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 2m, 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 Sis 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 3n. Theorem 3.1. Let 1nm GSP , then 2() 1 TG . Proof. By lemma 1.1, it’s need to prove 1Δ)( 2Gλ 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 4n, 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 w0,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,3nm 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. Copyright © 2010 SciRes. AM 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 mj1, 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. |