幾類樹圖的多級距離標(biāo)號

1、分 類 編 號 :密 級 :1丫位 代 W :10 0 6 50 9 2 0 5 0 1 2天 津 師 范 大 學(xué)研 究 生 學(xué)位 論 文論 文 題 目 ： 幾 類 樹 圖 的 多 級 距 離 標(biāo) 號學(xué) 生 姓 名 ： 侯 麗 霞 申請 學(xué) 位 級 別 ：理 學(xué) 碩 士申請 專 業(yè) 名 稱 ： 應(yīng) 用 數(shù) 學(xué) 研 究 方 向 ： 圖論 及 其 應(yīng) 用指 導(dǎo) 教 師 姓 名 ： 左 連 翠 專 業(yè) 技 術(shù) 職 稱 ： 教 授提 交

2、論 文 日期 ： 2012 年 3 月T h e m u lti -lev eld ista n ce la b elin g fo r S ev era lcla sses o f tre e g ra p h sA b s t r a c tT he m u l ti -l eveldi stan ce lab el ing for a con n ected grap h G al so cal ls th e rad i o

3、l ab eli n g .It i s am appi ng f :V {G )— ) ?{0,1， 2， … },so thatthe f ol l ow i ng i s sati sf i ed f or u ,u E V (G ):\ f (u)—f {v)\>diarr i(G )+ 1 —d ( u ,v),w here diam (G )i s the di am eter of G .d(u ,v)i s

4、 the di stance betw een u . v .T he span of f i s defi ned as m ax {f ( u )—f ( v)}-T he m ul ti -l eveldi stance num ber ofa graph Gu , V ￡ V (G )i s th e m i nim um sp an of al lm u l ti -leveld i stan ce l ab el i i

5、 i gs for G .A cl ass of sym m etri c b i n ary trees ab out root,sy m m etri c l obster trees ab ou t w ei ght cen teran d sy m m etri c sp i d ers trees ab ou t w ei ght center are i n vesti gated ,an d thei r l ow er

6、 b ound s of th em ul ti -l eveldi stance num b er are ob tai ned ,and then the ex act nu m b ers i n som e sp eci alcases of them u lti-le v e l d ista n c e n u m b e r a re o b ta in e d .T h i s p ap er is com p os

7、ed of th ree p arts:i n th e fi rst p art,i t i s i ntrod uced th at th e m u l ti -l eveldi stance l abel i ng ofsym m etri c bi nary trees aboutroot,and gi ven that了 2 4 6 … 21 ---2b ^ —、 ， ; ^, '>V x個I/ —

8、2)( “- 2)]+ 2(k —3)^fc +i+ — — — 5k + — ,i f A:= 5 or 7;k 2 x— k- 2 98 —2)(^-—2) ]+ 2{k —3)tk ± iH- — — — 5k + — ,i f k i s odd and k > 9;~ 2)( ti—2) ]+ Y ' k + hi t i s m ai n l y d i