超歐拉圖的判定及Catlin-猜想的研究.pdf

1、西南師范大學(xué)碩士學(xué)位論文超歐拉圖的判定及Catlin-猜想的研究姓名：王斌申請(qǐng)學(xué)位級(jí)別：碩士專業(yè)：基礎(chǔ)數(shù)學(xué)指導(dǎo)教師：李登信2003.5.1T h e D e t e r m i n a f i o n o f S u p e r e u l e r i a n G r a p h s a n d R e s e r c h o fC a t l i n - C o n j e c t u r eM a j o r “ B a s i c

2、 M a t h e m a t i c sS u p e r v i s o r ：P r o f ．L i D e n g x i nA b s t r a c tS p e c i a l i t y ： G r o u p & G r a p hA u t h o r ： W a n g B i n ( 2 0 0 0 2 0 7 )T h e s u p e r c u l e r i e ng r a p hp r

3、o b l e mi s a n i m p o r t a n t s t u d yi nt h ec i r c l eo f g r a p ht h e o r y , w h i c hm a i n l yi n c l u d e st w o a s p e c t s ：o n ei st h ed e t e r m i n a t i o n o f s u p e r e o l e r i s n g r a

4、 p h sa n d t h eo t h e r i st h ee d g e - p r o b l e m ．1 1 l cd i s s e r t a t i u ni n v e s t i g a t e dt h ep r o b l e m sm e n t i o n e da b o v eu n d e r t h ec o n 打a c t i o nm e t h o d I n t h e p a p

5、e r , t h e r ei s an c v Vc o n c e p t i o n - - s u b - c o l l a p s i b l es u b g r a p l r —一p r e s e n t e d ，a r o u n d w h i c h t l I ∞a ∞s o m e d i s e n s s i o a s m a d e ．n ”m a i n r e s u l t so f t

6、h e p a p e r 帆f o I l o w i n g ：T h e o r e m 7 G i s a s i m p l e g r a p h T h e n G ES Lc ，T h e r e a r e e d g e —d i s j o i n t p a t h sP I ，P 2 ，．P 。w h o s e c n d p o i n t s a r ed i f f e r e n t i n p a

7、i rs u c h t h a t O ( G 卜{ e n d p o i o t so f 只f f = 1 , 2 ，?S }Ja n d G —U E ∽) i s c o n n e o t e d ．i = l。P ∞p ∞“沁n3 ．2 I f 甄na 磚n a t u r a ln u m b e r s ，1 1 0l e s s t h a n2 ，t h e n 卅×”- 舒dg r a p h sa

8、r es u p e r c u l e r i a n w h e n m ，n a r e n o t 3s i m u l t a n e o m l y ．T h e o r e m8 S u p p o s eHi s as u b g r a p ho fac o n n e c t e dg r a p hGI fH i s a s u b - c o l l a p s i b l es u b g r a p h O

9、f G ．t h e n G ／I - I ∈S L §G ∈S L ．T h e o r e m9 A s s u m e ( 每( V E ) i s s u p e r e u l e r i a n ，I V ( G ) I - - n ，艿( G ) d e n o t e st h em i n i m a ld e g r e eo fG ．I f 占( G ) ≥m 雙{ 4 ，—n - - 4 ) ，t h

10、e n t h 盯e i s a s p 蛐J l i n ge u I e r i 孤s u b 鯽p hH s u c h t h a t| E ( t ／) l ≥妄l 以G HT h e o r e m1 0 A s s u m e G = ⅣE ) i s s u p e n m l e r i e na n dk 3 一／沁e ，I V ( G ) I = n ，艿( G ) d e n o t e s t h em i I

11、 I i m a ld e g r e e o f G ．I fJ ( G ) 2 而g ／，t h e nt h e r ee x i s t sa s p a n n i n g e u l e r i a ns u b g r a p h H ，s u c h t h a t陋餌1 2 導(dǎo)l 耳G M ，甜岫℃眥訂晌i b r a n c h e s i n G ．E ㈣．P r o p o s i t i o n6 ．1 H i

12、 s as i m p l eg r a p h ．I ft h e r ei s 缸e v e l ls e tX o fV ( H ) s u c ht h a te v e r ys u b g r a p h H ro f H w h o s e o d d - v m 憶' x s o t i sX i sn o t s p a n n i n go n e , t h e n t h e r e i sa s u p

13、 o r g r a p hGo f H ．s u c h t h a t G ，H E S L §G ∈S L f a i l s ．K e y w o r d s ：S u p e r e u l e r i a n G r a p h s ；C o l l a p s i b l e ；C o n t r a c t i o n ；S u b - c o l l a p s i b l eS u b g r a p h