含邻域条件的独立树_英文_

含邻域条件的独立树_英文_ () 2001, 14 1: 56, 59 ΞIn depen den ce Trees In volv in g Ne ighborhood Se ts 1 2) ) ((2肖新平, 2何崇仁X IAO X inp ing H E C hongren (1. . . . , . . . , 430074,D ep tof C on t rol S ci& E ngH uaz h ong U n ivof S ci& T echH ubei W uh an 2. ; . . , . , 545005, C h inaD ep tof M a thand P h y sicsG uang x i I nst itu te of T echG uang x i L iuz h ou )C h ina : , A bstra ctU sing va r iou s ne igh bo rhood cond it ion sw e ob ta in tw o new re su lt s re la ted to indep endence .t ree s : ; ; KeywordsIndep endence t reeH am ilton ian g rap hN eigh bo rhood () 1991: 0570 AM S Subject C la ss if ica t ionC CL C Num ber: O 157. 5 () : : 100129847 20010120056204D ocum en t codeA A r t icle ID W e u se 4 fo r ba sic term ino logy and no ta t ion no t def ined h ere and con sider sim p le g rap h s () (. G n, v N G v on lyL et be a g rap h of o rder th e neigh bo rhood of a ver tex is deno ted by o r ()() ) N v , u v d G u , v . C th e d istance betw een tw o ver t ices and is deno ted by Fo r a cycle w ith a + - () v ? V C , v v C v g iven o r ien ta t ion and ver tex w e u se fo r th e successo r of on and fo r it s + + () Α V C , A ={v v ? A }. |T G p redecesso r. If A th en A sp ann ing t ree of is ca lled an ) ( is an indep endence t ree, if th e set of end ver t ices of ver t ices w ith deg ree one inT T ( ) indep endence set in G. L et k ? 1, an I = k 2 t ree I ?k 2t ree, I ?k 2t reeof G is an indep endence t ree of () G k G. I 2 , w ith a t m o sta t lea stend ver t ices o r a H am ilton cycle of It is obv iou s th a t ?2 t ree is a ( ) ( G I 2 H am ilton p a th if is a nonh am ilton ian g rap h and ?1 t ree is th e sam e a s a H am ilton cycle if ) G ? K , I 2 S -. 1 so th en an ?k t ree can con sidered a s a genera liza t ion of a H am ilton g rap hA n ?k t ree G G k G. , of is sp ann ing t ree of w ith a t m o st end ver t ices o r a H am ilton cycle of S im ila r lyw e S 2t ree S 2t ree. , , K deno te = k and ?k O n th e o th er h andfo r conven iencew e in t roduce th e cla ss of a ll G g rap h s no t con ta in ing an indep endence t ree. B y th e m a in resu lt of 1 , h a s an indep endence G | K , G ? K t ree if and on ly if and every ver tex of a connected g rap h is th e end ver tex of a G.H am ilton p a th of D eg ree cond it ion s h ave long been a fundam en ta l too l in th e study of h am ilton ian p a th s and . h am ilton ian cyclesR ecen t ly m any resu lt s app ea red in w h ich cer ta in ver tex set s a re requ ired to . h ave la rge neigh bo rhood un ion s and neigh bo rhood in ter sect ion s in stead of la rge deg reeT h ree Ξ Rece ived da te: M a rch 24, 2000 : Founda t ion itemT he w o rk is suppo r ted by the sp ecia l fund of the Science and E duca t ion D ep a r tm en t of the M in ist ry of such resu lt s a re th e fo llow ing: () () () 1 7 Theorem F aud ree G 2n, |N u ?N v | ? n 2If is a connected g rap h of o rder and - ? - 1 fo r every p a ir of nonad jacen t ver t ices u , v , th en G is t raceab le. () () () 2 7 G 2n, |N u ?N v | ? n - 2Theorem F aud ree If is a connected g rap h of o rder and ? u , v , G .fo r every p a ir of nonad jacen t ver t ices th en is h am ilton ian () () () 3 3 Theorem C h en G 2n, m ax {d u , d v } ? nƒ2 2If is a connected g rap h of o rder If () () u , v ? N u ? N v ? Α - 1, G 1 || fo r every p a ir of nonad jacen t ver t ices w ith th en is.h am ilton ian , 1 U sing th e indep endence t reesw e f ir st ob ta in a comm on genera liza t ion of T h eo rem and 2 :T h eo rem a s fo llow s () () 4 G n ? 3, N|u ?N v ? n - ? - k + 1 fo r a ll | Theorem L et be a g rap h of o rder and () u v G k ? 1, G I 2t ree. nonad jacen t ver t ices and of th en h a s an ?k () G ΑG , If h a s an indep endence t reeth en t deno tes th e m ax im um num ber of end ver t ices of () () () () G , , ΑG ? ΑG ΑG - ΑG 1 .indep endence t ree of clea r lyt and t can be a rb it ra r ily la rge () (), ΑG 3 ΑG . T h u sit w ou ld be n ice if w e cou ld p rove th a t in T h eo rem can be rep laced by t In () () , ΑG ΑG :factw e can show th a t a sligh t ly w eak er resu lt ho ld s w ith rep laced by t () () 5 G 2n, m ax {d u , d v } ? nƒ2 2Theorem L et be a connected g rap h of o rder If fo r every () () u , v ? |N u ? N v | ? Α, G 1 .p a ir of nonad jacen t ver t ices w ith t th en is h am ilton ian 1, 2, 5, 6 :T h e fo llow ing L emm a s a re u sefu l to p rove ou r m a in resu lt s G G I 2t ree S 2t ree. , L emma 1 If is a g rap h th en h a s an ?k if and on ly if it h a s an ?k G ? K G I 2t ree k., If 2 is a connected g rap h th en h a s an ?k fo r som e 2L emma G ? K l If a g rap h 2 h a s a sp ann ing t ree w ith end ver t ices such th a t th ere a re tw o3L emma , G S 2t ree. ad jacen t end ver t icesth en h a s an ?l- 1 θ 4 G G.L emma is h am ilton ian if and if is h am ilton ian 5 G 2n, G 2L emma L et be a connected g rap h of o rder th en con ta in s a cycle p a ssing th rough 1ƒ2 n.a ll ver t ices of deg ree a t lea st 4 1, k ? 2. Proof of Theorem B y T h eo rem w e on ly need to p rove th a t resu lt ho ld s fo r O n , 1, G S 2t ree. th e o th er h andby L emm a w e w ill focu s ou r a t ten t ion on p rov ing th a t h a s an ?k () 2, G S 2tree T , . l >U sing L emm a h a s an = l deno ted by w h ere l is cho sen a s sm a ll a s po ssib leSo k G S 2t ree. 3, u v and does no t h ave an ?l- 1 B y L emm a w e m ay a ssum e th a t and a re nonad jacen t T. end ver t ices of T h en () () N - ? - k + 1 ? n - ? - l + 2|u ? N v | ? n k ? 2, TS ince l > is a sp ann ing t ree w ith a t lea st 3 end ver t ices. L et w be th e th ird end ver tex of - - - () () () T , x ? w , x x ? N x , d x , w < d x , w , fo r a ver tex choo se such th a t T T T w e now :p roceed w ith th e p roof of th e fo llow ing cla im s - () ()() 1 If w x ? E G and w ? x ,d x =2. C la im th en T -- - () () w x - x x w ? x , d x ? 1. d x ? 3, T + S ince cer ta in ly T T h u s T w h ich im p lies is an - () S 2t ree. d x =2. ?l- 1 T h is con t rad ict ion p roves T - - ()() ()() 2 E G , v x | E G . w x ? E G , u x | C la im If th en - - - () () () ux ? E G , 1d x = 2, T + w x - x x S 2t ree Suppo se th a t by C la im T th en is an = l in --x S G t ree, w h ich is a 3, w h ich and u a re ad jacen t end ver t ices. B y L emm a h a s an ?l- 1 - ()v x | E G . con t rad ict ion. S im ila r ly, B y L emm a 3, w e m ay a ssum e th a t th e end ver t ices set of T is an indep endence set. C la im - ( ) ( 2w y y =) im p lies th a t fo r every ad jacency of excep t fo r such th a t w , th ere is a d ist inct () () ()w - u v. f ?N{y } ? N u ? N v nonad jacen t ver t ices of and T h u s w e def ine th e funct ion - () ()x f x = x ? V T . by fo r l F rom th e p rev iou s a rgum en t s th e funct ion is clea r ly in jeet ive, con sider ing th a t T end h a s ) ( u v , ver t ices includ ing and w e h ave th a t () () () () () N u ? N v ? N G - N w - 1- l ? n - ? - l + 1, || || || . , 4 .w h ich is a con t rad ict ionT h erefo reth e p roof of T h eo rem is com p leted θ = 5 4, GB.Proof of Theorem B y L emm a w e on ly h ave to show th a t is h am ilton ianL et θ () () () {v ?V G | d v ? nƒ2}. 4 5, GB ,G U sing L emm a and w e get is a com p lete g rap h and th ere θ C GB . , C ex ist s a cycle in con ta in ing a ll ver t ices of A m ong a ll such cycleslet be one of m ax im um leng th. S ince G is 22connected, th ere ex ist k ? 2 d isjo in t p a th sQ 1 , Q 2 , , Q k f rom som e ver tex x () () ? V G V C v 1 , v 2 , , v k of C. A ssum e th a t v 1 , v 2 , , v k a re num bered ƒto d ist inct ver t ices (){v , v , G , N x = 1 2 , v k }. O b serve th a t th ere acco rd ing to a f ixed cyclic o rder ing of and let C m u st be a t lea st one ver tex betw een x i and x i+ 1 th a t is no t an endpo in t of a p a th , o r else a cycle C .longer th an resu lt s .T h e p roof is b rok en in to a num ber of sta tem en t s each of w h ich is p roved w h en p resen ted + + () () () 1d v + d v < n. i j τ σ + ++ ++ ++ θ() v , v ( ) v v ? N x ? E G , v C v v C v x v GIf th ere is such th a t i j i j th en ij i j i is a cycle in C + B C , . N ( x ) con ta in ing a ll ver t ices of longer th an con t ra ry to th e a ssum p t ionT h is im p lies th a t is C . , 4, i, j ? {1, 2,, k }, i ? j ,an indep enden t setF u r th eracco rd ing to L emm a it is clea r th a t fo r + + () ( ) d v +< n. v th en i j d ()2 k ? Α.t + + + TC \ {v v , v v , = , v v } ? {Q , Q , L et 1 1 2 2 k , Q k }, th en T is a t ree w ith end ver t ices set k 1 2 + () () () . = x V G \V T N 5 , T I 2t ree, C w h ich is an indep endence setIf th en is an = k o r else w e a re () ()G. W= V G \V T of I 2t ree and let H 1 , H 2 , , H t be th e P u t go ing to con st ruct an ?k G [W .com ponen t s of th e g rap h () , t, N C x , Fo r each H s , s = 1, 2, it h a s a t m o st one neigh bo r in o r else longer cycle ( . K , H s P s H s resu lt sA cco rd ing to th e def in it ion of w e ob ta in th a t eith er h a s a H am ilton p a th if ) () .? K T H | K o r h a s an indep endence t ree s s () () () u? V H , v ? N x uv ? E G , If s s s C such th a t ss let t t ϖ ϖ ( () ) ( () ) T=T ? ? {u v } ? P o r T=T ? ? {u v } ? T , ss s ss s s= 1 s= 1 ϖ TI 2t ree.th en is an ?k ′′() () ()() u s ? V T , y ? V T ƒN x u s y ? E G , let If s s C such th a t s t ′ϖ ′ϖ ( () ) () ) T= T ? ? y } ? P r T=T ? {u y } ? T , s s {u s s o s s s= 1 ϖ TI 2t ree.th en is an ?k + () () () 3N x ? N v ? k. || i + +() (( ) ( ) ( ) ) u ? Nx ? N v , u | u x ? EG , u v i ? E GV C , If th ere ex ist s i th en , w e deduce + τ θ x uv C v xth a t i i is a cycle in G con ta in ing a ll ver t ices of B longer th an C. T h is con t rad ict ion show s + () () x ? N v | ? k. i th a t N | +( )() () 2 ( ) 1 ? N? k ? Α. t F rom th e cond it ion of || and x ? N v B y 3, it fo llow s th a t i ++ (5, d v ) ( ( ) ( ) ) m ax v ? n2.ƒT h eo rem w e h ave = d x , d i i + + + () ( ) ( ) v + v d v j ? n2. di i ? n,ƒS im ila r ly, d a con t rad ict ion. T h ese y ield :Ref eren ces 1 B roe r sm a H , T u in st ra H. Indep endence T ree s and H am ilton C ycle s[J . J. G rap h T h eo ry 1998, 29: 227, 237. , , , , . 2 Bohm e T B roe r sm a H J Gobe l F Ko stoch k a A V S t ieb itz M N o te sp ann ing t ree s w ith p a irw ise 1997, 170: 219, 222.nonad jacen t endve r t ice s[J . D iscre te m a th. 3 C h en G. H am ilton ian G rap h s Invo lv ing N e igh bo rhood In te r sect ion s[J . D iscre te M a th. 1993, 112: 253, 257. , . [. : , 4 Bondy J A M u t ry U S RG rap h T h eo ry w ith A pp lica t ion sM N ew Yo rkM acm illanL ondon and , 1976.E lsev ie r . [. . . . 1984, 37: 221, 227. 5 F an GN ew Suff icien t Cond it ion s fo r C ycle s in G rap h sJ JCom b inT h eo ry B . 22, 271.[. . 1992, 16: 2676 Sh i RN e igh bo rhood s and H am ilton ian Cond it ion sJ JG rap h T h eo ry , , , . F aud ree R J Gou ld R J J acob son M SL en iak L M N e igh bo rhood U n ion s and H igh ly H am ilton G rap h s 7 [. . , 1991, 31: 139, 148.J A r s Com b in 含邻域条件的独立树 1 2肖新平, 何崇仁 ( 1. 华中理工大学控制科学与工程系, 湖北 武汉 430074; 2. 广西工学院数理部, 广西 柳州)545005 摘要: 本文利用不同的邻域条件, 得到了两个与独立树有关的新结果. 关键词: 独立树; 哈密顿图; 邻域