《k连通图中的k可收缩边》由会员分享，可在线阅读，更多相关《k连通图中的k可收缩边（27页珍藏版）》请在金锄头文库上搜索。
1、广西师范大学 硕士学位论文 k连通图中的k可收缩边 姓名：杨迎球 申请学位级别：硕士 专业：应用数学 指导教师：苏健基;袁旭东 20070301 kk ): H: ?R ;:A;:c?: 2004? XJkG ?E,k,KGk , .K .XJk3 ,K8B yk, 5,d k.3k.exy3 n/xyz, d(z) = k,xy , . 1961c, Tutte3(1)y ?53k .uk 4, Thomassen 3(2)y 3kkKk .k3 , .Nw .kz5k 3 .Jyvk .12,dTuttey( .3. .4Fonet(3)Martinov(4)/ x:eGvk 4,KG,4
2、3K .x .5x .4(J,8vk( J,x .k .?ck SN .k5,ddk3 . 1981c,Thomassen3(2)y Xen: nAG k,KGkn/K3. =,ekGn/,KG3k , Egawa3(5)O n /k ,y : nBzn/kG,?kmin|V (G)| + 2 3k 2 3k,|E(G)| . nBn/kk? .n/5 3q?r .Egawa3(6) kk ?,y X en: nCk 2 Gk,(G) 5k 4 ,KGkk . 2 k 3, G?uKk+1. eGvkf?uH,GH-free.K 4 LlK4? ,Kawarabayashi3(7)y : I
3、nD (7)k 3,eGK 4 k,KGk . o?K 4 -free k ?,3(8) K 4 -free k e.: nE (8)k 5GK 4 -free k,KGkk + 1 . n/3 . Mader3(9)y .k kn/, : nF (9)G .k,KG?k|V (G)| 3 n/. CKriesell3(10)U? Mader(J,y .k? k2|V (G)| 3 n/. bowtiedTk?:n/?/,CAndo,KGkbowtie. =,ek (k 4)Gbowtie KGk Lc?bowtie-free k,31Xen: n1Gbowtief,HfkKG?kk .(k
4、4). (H = kK1+K2uy,vx+xy,K2= uv,x,y V (kK1),=Hk4, T Tk3k 2n/). f,n1ke.e. n2Gbowtie,(k 2)K1+K2k,KG?k2k .(k 4). 1?4?kk Bf.Gk( 2),e ?e E(G)kGe2k,KG4?k.kG,XJG 4?k,3?k5cJe,LKG , 4?k,dzkk4?kf.w,XJGH-free,K? fH-free,XJGkfk e,oeG .d?4?k3 k. Ando3(12) e(: nHG4?k (k 5),K1+C4, ?k:x V (G),E(x) k3?n/,KGkk . 4?k ,
5、 3(13)y ,3k 8,e4?kG P = K1+2P3, XJG?k:x,3x3n/,oGkk . ?K1+ C4,Juy,K1+ C4=P3+ 2K1.31 e(: n3e4?k (k 5)GP3+3K1, G?k:x V (G),E(x) k3?n/,KGkk . ?E 5K5,kK1+ C4,?P3+ 3K1,z5:3n II /,n3,?vnH, N?y,Gk .l fw,n35 3nH .d n3,g,?2n3, e(: n4GP3+ tK14?k, G?k:x V (G),E(x)k 3n/,K?k 4t 1,Gk .(t 4). c:k, ,bowtie-free,4?k
6、III k Contractible Edges in k Connected Graphs Author: Yang YingqiuSupervisor: Prof. Su JianjiYuan Xudong Major: Applied MathematicsSpeciality: Graph TheoryGrade: 2004 ABSTRACT An edge of a k connected graph G is said to be k contractible edge, or simply contractible edge, if its contraction results
7、 still in a k connected graph.An edge that is not contractible is called a non- contractible edge.If a k connected graph has contractible edge,then we can prove some problems which related to connectivity of it by inductive approach. Hence,it is useful to study contractible edge.In a k connected gra
8、ph,if edge xy is contained in a triangle xyz and d(z) = k, then xy is called trivially non-contractible. In 1961, Tutte (1) proved that any 3 connected graph with order at least 5 has a contractible edge. On the other hand, Thomassen (2) showed that for k 4 there are infi nitely many k- connected k
9、regular graphs which do not have a contractible edge.In order to get some conditions of having a contractible edge in k connected graph ,the defi nition of contraction critical k con- nected graph have been introduced. A noncomplete k connected graph G is called contraction critical k connected if i
10、t has no contractible edge.It is easily to see,if we deny every property of a contraction critical k connected graph,we can obtain a suffi cient condition about the existence of contractible edge in k connected graph.We can easily prove that there are not contraction criti- cal 1 or 2 connected grap
11、hs.By Tuttes result he proved above,there are not contraction critical 3 connected graphs too.The contraction critical 4 connected graphs was characterized by Fontet(3) and Martinov(4),that is:Let G be a 4 connected graph without contractible edge ,then G is either a square of cycle or a line graph
12、of cyclically 4 connected 3 regular graph.It is harder to charac- terize contraction critical 5 connected graphs than to characterize contraction critical 4 connected graphs.Up to now, there are no satisfi ed results about such things,let alone to characterize any general contraction critical k connected graphs.Recently,it is important to study the property of contraction critical k connected graphs,then,come out some suffi cie
