确定某些对虾树的优美性_英文_

确定某些对虾树的优美性_英文_ 1 21 赵梅梅 谢继国 姚兵 ( 1. 西北师范大学, 甘肃兰州 730070; 2. 兰州城市学院, 甘肃兰州 730070) 摘 要: 众所周知, 优美树猜想( GTC) 自 1966 年 Rosa 提出到今天已经成为一个非常著名的未解决的问题, GTC 问题最初来自于把完全图 K分解成同构于任意一棵预先指定的 n 条边的树的 2n+ 1 个子图. 尽管有大 2n+1 量的有关 GTC 的文章发, 但彻底解决这个猜想还很遥远.故而, 人们把研究 GTC 的范围缩小到一些特定类 型的树上来, 如 Bermond 的猜想: 每一棵对虾树都是优美的( 1997) .由此启发, 我们确定了几类对虾树的优美 性, 并提出了几个问题以供进一步研究. 关键词: 全染色; 优美标号; 对虾图; 树 中图分类号: 0157.5 文献标识码: A 文章编号: 1008- 9020( 2008) 02- 011- 03 1. Introduction and concepts The following Graceful Trees Conjecture ( GTC) had been Suppose that a radio astronomer needs to place satellite found by many researchers: [4] dishes along a straight line in such a way that every possible Conjectur e 2.(Rosa,1966) Every tree is graceful. It is noticeable that GTC is still open up to now despite , 2, , n is a achieved between some pair of them. distance 1 the tremendous work.There are a few number of results on GTC One way to accomplish this would be to put a satellite at posi- although Bing Yao et al. proved a graceful tree whose maximum tion 0,then another at 1,then another at 2,and so on through n degree is not less than the half of number of its vertices( cf.[4]) (thus using n+1 satellite dishes).We could make this ruler into a graph by replacing each satellite dish with a vertex of the A caterpillar is a tree T such that the graph obtained by graph, and putting edges whenever the distance between two deleting all leaves from T is just a path, where a vertex of de- satellite dishes is used. Such a labelling is what Golomb called gree one is called a leaf. A lobster H is tree such that the graph a graceful labelling of the graph( cf.[1],which is then said to be obtained by deleting all leaves from H is a caterpillar.One may graceful.) consider the following conjecture that is very simpler than GTC. [4] All graphs considered here are finite and undirected,and Conjectur e 3.(Bermond,1979) Every lobster is graceful. contain no loops and no parallel edges.Standard graph- theoreti- Our work is motivated from Conjecture 3. Surprisingly, it is cal terms not defined in this paper can be found in[2] and[3]. easy to prove the gracefulness of a caterpillar,but it seems to be Definition 1. If a proper labelling f of a graph G is an in- very difficult for the gracefulness of lobsters. [4] jection from V( G) into the set {0,1,..., |E( G) |}such that the la- Definition 2.A graceful labelling f of a tree T is said to bel of an edge uv is |f ( u) - f ( v) | and all edge labels of G are be ordered graceful ( bipartite graceful) if for every three ver- pairwise distinct. In fact, all edge labels are consecutive.Then f tices x,y and z of the tree T with xy,yz?E( T) we have either is called a gracful labelling of G,and G is termed to be a gracful (f x) <(f y) and (f z) <(f y) , or (f x) >(f y) and (f z) >(f y) . graph .We often say that G admits the graceful labelling f. Definition 3.Let f be a labeling of a graph G, we defined Alexander Rosa, 1966 - 1967,discovered that if each tree the dual labeling h of f as this:h( u) =max( f) +min( f) - (f u) for all vertices u?V( G) . admits a graceful labelling,then this will settle a longstanding, well- known Ringel- Kotzig Decomposition Conjecture in popu- 2. Results and pr oofs larization( cf.[4]) We illustrate several symbols before start the following.Let [4] Conjectur e 1.( Ringel and Kotzig,1963;Rosa,1967) Any L (T) denote the set of all leaves of a tree T. A path with n +2 complete graph Kcan be decomposed into 2n +1 subgraphs vertices is written by P=aaaaa.Let N( u) denote the set 2n +1 0 1 2 n n+1 which are isomorphic with a given tree with n edges. of all vertices that are incident to u. A star is a tree with n +1 收稿日期: 2007- 08- 28 作者简介: 赵梅梅( 1986—) , 女, 甘肃宁县人, 西北师范大学数学与信息科学学院在读生, 研究方向为图论及其应用. 确定某些对虾树的优美性 赵梅梅等: 第 13 卷第 2 期( 2008) Vol.13 No.2( 2008) Pr oof. Let Y=Y( n+1, A( i) , t) described above.Since V( Y) = vertices and n leaves,often we represent a star by K.A double 1,ni n i ( ) ( ( ) ) , ( ) , ,, n, n + VP??VSwhere VP={a|i =01star Sis a tree only with s+t leaves and two center verticesn ( ) s+1,t+1 i=1 di+1,t+1 i band asuch that N( b) ={b, b, , b, a}, N( a) ={c, c, i i ii, 1i, 2i, siii, 1i, 21}, V( S ) is described by the form( 1) , where d( i) =i for 1% i+1,t+1 i i , , ( ) ( ) ( ) cb}and VS=Nb?Nawhere integers s 1"i, iiii s+1,t+1 i%n. It is easy tp compute |V( S ) | =t+i+2 for 1%i%n.Hence, the i+1,t+1 i and t0.Clearly,for t=0 the double star Sbecomes a star." numbefr of vertices of Y equals to s+1,1 n |V( Y) |=n+2+ ( t+i+2) =n( t+3) +2+n( n+1) /2.The graph identity operation between two graphs H and G (i=1 products a new graph by identify a vertex u?V( H) with a ver- For the purpose of convenience,let m- 1=|V( Y) |.We are ready to tex v?V ( G) into a new vertex w of X.We define some classes present a labeling f of Y in the following: of lobsters as follows. a1. (f a) =m, (f a) =0,(f a) =m-( t+1) , (f a) =4+t. 0123i a2. ( f b) =m-( t +2) , f( b) =3 +t, f( b) =1, f( b) =n -( t + 121,12, 11. Z- type lobster s.Let P and Sbe a path and a dou-1 s+1,t+1 ) , (f b) =m-( t+3) .(f b) =2, (f b) =t+4+1, (f b) =(f b) +1. 42,23, 13, 23,33, 2ble star described above,respectively.For integers s 1, t 0 ""() , () a3. f c=m- j for 1%j%tf c=2+j for 1%j%t. 1,j2,ji , ( ) and 1%i%nwe identify the vertex a?VSwith the ver-i s+1,t+1 (f a ) -( t+i) , i is even and i"4 i- 2 a4. (f a) = . tex a?V( P) into a new vertex,for the purpose of convenience, i’i(f a) -( t+i) , i is odd and i 5 " i- 2 we write this new vertex by astill. Hence, the resulting tree is i (f b) -( t+i+1) , i is oddn and i3" i- 2 just a lobster,denoted by Z ( n+1,s,t) .Clearly, a Z- type lobster 1(f b) = . i’ i is even and i" 4 () ( ) ,f b-t+i+1 i- 2 Z(n+1,s,t) has the set of all leaves as this: 1 a5. If i is even and i"4, (f b) =(f b) -( t+i) , and i,ii- 2, i- 2, , ,, L( Z(n+1,s,t) ) ={c, c, , b|i=1,2, , n}. cbb 1 i,1i,2i,si,ti,1i,2() () f b=f b- j for 1%j%i- 1. i,ji,i2. Z- type lobster s.Let P=aaaaabe a path where n 2012 nn+1 i If i is odd and i5,( b) =(f b) +( t+i) , and (f b) +( t+ "i- 2, 1i,1 i,1 is odd, and Sbe a double star described above.Let integers s+1,t+1 3) +j- 2 for 2%j%i. s"1, t"0 and. For each odd integer i"1, we identify the vert ( ) ( ) , c-t+j+1i is odd and i3h" i- 2, j i a6. (f c) = ( ) ( ) , ex a?VSwith the vertex a?VPinto a new vertex, for theij’ii s+1,t+1h( c) -( t+j+1) , i is even and i" 4 , i- 2j purpose of convenience,we write this new vertex by astill.For i for 1%j%t. i , ( ) each even integer i2we identify the vertex a?VSwith"i It is not hard to verify that the edge labels of Y is {1, 2, , m}. 1,t+1 the vertex a?V( P) into a new vertex, write it by a. Hence, the iiTo show that there is another graceful labeling h such that resulting tree is just a lobster,denoted by Z(n+1,s,t) .Clearly, a h is not the dual labeling of f, it is sufficient to give h in detail. 2 Z- type lobster Z(n+1,s,t) has the set of all leaves as the following: 22 b1. h( a) =m, h( a) =0,h( a) =m- t, h( a) =5+t. 0123L( Z(n+1,s,t) ) ={b, b, , b|i=1, 3, , n}?{b, b, , b}? b2. h( b) =m-( t+2) , h( b) =3+t, h( b) =1, h( b) =n-( t+ 2 i,1i,2i,s12n121,12, 1 , , ,c|1%i%n}. {cc4) , h( b) =m-( t+3) .h( b) =2, h( b) =3, h( b) =6+t. i,ti,1i,2 2, 23, 13, 23, 3i b3. h( c) =m-( t+1) , h( c) =h( c) +j for 2%j%t. 1, 11, j1, 1( ) A i- ser ies lobster s. Let Sbe a double star with3. d( i) +1,t+1 h( c) =h( a) - 1, h( c) =h( c) - t- 1+j for 1%j%t- 1. i 2, t32, j2, t, ( ) ( ) ( ) , the vertex setVS=Nb?Nawhereii ( ) di+1,t+1 ( a ) -( t+i) , i is even and i4 h"i- 2 b4. , ( a) = hN( b) ={b, b, , b, a}N( a) ={c, c, , c, b} ( 1) i’ii,1i,2iii,1i,2i,ti, ( ) idih( a) -( t+i) , i is odd and i5 " i- 2 i ( ) Now,identifyingt he vertex a?VSwith the vertexi ( ) di+1,t+1h( b ) -( t+i+1) , i is oddn and i"3 i- 2 ( ) = . h b a?V( P) into a new vertex,still write it by a, yields a new lobster i’ iih( b ) +( t+i+1) , i is even and i 4 "i- 2 which indicated by Y( n+1, A( i) , t) where A( i) ={d( 1) , d( 2) , , b5. If i is even and i4, h( b ) =h( b ) -( t+i) , and ", i,i i- 2i- 2 d( n) } and called a A( i) - series lobster.Needless to say that A( i) - h( b ) =h( b ) - j for 1%j%i- 1. , , ij ii series lobster Y( n+1, A( i) , t) will provide us many interesting lob- If i is odd and i"5,( b ) =h( b ) +( t+i) , and h( b ) = , i- 21 i,j i,1 sters for different set A( i) .For A( i) ={d,2d, , nd}, that is ,all ele- h( b) +( t+3) +j- 2 for 2%j%i. i,1 ments of A( i) forms a arithmetic progression, where integer d1, " h( c) -( t+j+1) , i is odd and i3" we call Y( n+1, A( i) , t) a d- rainbowl obster. i- 2, j b6. h( c) = , ij’ h( c) +( t+j+1) , i is even and i4 " i- 2, j Theor em 1. If A ( i) ={1,2, , n} provided odd n,then for 1%j%t. every 1 - rainbow lobster Y ( n +1, A ( i) , t) admits at least a By the construction of two graceful labeling described ordered graceful labelling for all integer t1.Furthermore,(Y n+ " above,it is not hard to understand thae both are ordered.The 1, A ( i) , t) has at least two ordered graceful labellings in which proof is completed,as desired. one is not the dual labeling of other one. 12 第 13 卷第 2 期( 2008) Vol.13 No.2( 2008) ( a) : Theor em 4. Every Z- type lobster Z( n +1, s, t) is ordered 1 1 graceful for s!t- 1. ( b) : For the proof of Theorem 4 is the analogues of other theorems above, so we provide two examples for illustrating Figure- 1.Two examples Theorem 4 as follows. The following results follows that proof of Theorem 1 as we take t=0 in the graceful labeling f described above. ( a) : Theor em 2.For A ( i) ={1, 2, , n} and t =0, every 1 - rainbow lobster Y( n+1,A( i) , 0) is ordered graceful. Theor em 3.If t!s- 1, then every Z- type lobster Z( n+1, 22 ( b) : s, t) is ordered graceful. Figure- 3. Two examples of Theorem 4. Pr oof. Let G=Z( n +1, s, t) and n =| Z( n +1, s, t) | . The 2 2 following is a ordered labelling f of G as if ts- 1. !Futur e possible wor ks 3. n} and n is even,determine , 1. (f a) =n;(f c) =n- j for 1"j"t-( s- 1) ;(f a) =n-( t- s+2) Pr oblem 1.For A( i) ={1, 2, 02, 1j whethe r every d- rainbow lobster Y ( n+1, A ( i) , t) is graceful or () f c=n- j for t- s+3jt. "", 1j ordered graceful for all integer t1. !() ;() ;() ;2. f a=0f b=j for 1"j"sf b=s+j for 1"j"s1 1, j 3, j Pr oblem 2. For A( i) ={d, 2d, , nd}where integer d2 or d= !(f b) =1+2s;(f c) =1+2s+j for 1"j"t. 2, 2j 1 and n is even,determine whether every d- rainbow lobster Y( n+1, () ( ) , f a-t+2i is even and i!4 i- 2 A( i) , t) is gracful or ordered graceful for all integer t!0. (f a) = 3. . i# () ( ) , f a+t+s+2i is odd and i!5 2ni- 2 Pr oblem 3. For A( i) ={q, q,...,q}where integer q2, ! () ( ) , !f b-t+2i is odd and i3 i- 2 determine whether every d- rainbow lobster Y( n+1,A( i) ,t) is . (f b) = i# () ( ) , !f b+t+s+2i is even and i4 graceful or ordered graceful for all integer t0. !i- 2 (f c) -( s+2) , i is odd and i3! i- 2, j 4. (f c) = ; , ij# Refer ence: 4 (f c) +( t+s+2) , i is even and i! i- 2, j [1] S.W.Golomb. How to number a graph in Graph Theory () () ( ) , () () f b=f b+t+s+2for i is odd i!5f b=f b+j for, i,1i,1i1 i, j and Computing. R.C.Read, Academic Press, New York,( 1972) 2js and i is odd and i5. ""!pp.23- 37. The rest work is to verify that the set of all edge labels of [2] J. A. Bondyand U. S. R.Murty. Graph Theory with Applica- G equals to {1, 2, , n}.We can omit it since it is easy. tion. Macmillan, NewYork, 1976. [3] Bela Bollobas, The Modern Graph Theory, Springer- Verlag, New York,1998. [4]Joseph A.Gallian. A Dynamic Survey of Graph Labeling. The Electronic Journal of Combinatorics 14( 2007) , #DS6. Figure- 2. Illustrating the proof of Theorem 3. Towar d to the gr acefulness of some lobster s 1 21ZHAO mei meiXIE Ji guo YAO Bing ( 1. Northwest Normal University, ,Lanzhou 730070; 2. Lanzhou City University, Lanzhou 730070) Abstr act:As we have known, the Graceful Trees Conjecture( GTC) is a longstanding conjecture posed by Rosa in 1966 since it comes from attacking the famous conjecture:any complete graph Kcan be decomposed into 2n+1 subgraphs which are isomorphic with a 2n+1 given tree with n edges. Despite the tremendous work,someone suggest to attack GTC in some small areas,such as Bermond conjecture that every lobster is graceful in 1979. Motivated,we discuss the gracefulness about some interesting classes of lobsters. Keywor ds:proper total coloring; graceful labeling; lobsters; trees 责任编辑: 蒋德璋 13