图论是离散数学中一个重要研究领域.它在计算机科学,化学,社会科学和生物学等方面都有很广泛的应用.　　 连通图的构造是图论中一个非常重要的研究课题.它与网络模型和组合优化联系密切,使它具有重要的理论价值和应用价值.自1961年,Tutte利用3连通图中可收缩边的存在性给出了3连通图的构造方法之后,人们致力于研究各种类型连通图的构造.可收缩边和可去边这两个概念不仅在连通图的构造上发挥重要作用,而且还是递归证明图的某些性质的重要工具.本文第二章至第四章主要研究连通图中可收缩边和可去边的性质以及他们在特定子图上的分布情况.　　 第二章主要研究了不含三角形的k连通图中收缩边的一个性质.设 G是k连通图,e=uv是图 G中的一条边.用G/e表示从图 G中删除顶点 u,v,并添加新的顶点 ve使得 ve与 u,v所有的邻点相邻所得到的图.如果G/e仍然是k连通图,那么 e=uv称为图 G的k可收缩边.不存在k可收缩边的非完全k连通图称为收缩临界k连通图.对于k=3,Tutte[83]证明了阶大于4的3连通图存在3可收缩边,所以不存在阶大于4的收缩临界3连通图.对于 k=4,Martinov和 Fontet分别证明了收缩临界4连通图 G是4正则的,且每条边恰在一个三角形上,即 G或者是 Cn2或者是7/2-边连通立方体的线图[32][59].这里7/2-边连通立方体可由 K4或 K4,4中去掉1因子的图通过构造的方法得到.当5≥5时,收缩临界 k连通图的结构比 k=3和 k=4的情况复杂得多.所以对于k≥5的情形,人们一般考虑收缩临界七连通图的局部结构.1982年,Thomassen[81]证明了收缩临界k连通图含有三角形,即如果k连通图G不含三角形,那么 G中存在一条边 e=uv使得任何k点割都不同时包含顶点u和v.最近,Fujita等[37]证明了如果k连通图G的最小度至少是[3k/2]+2,那么G有一条k可收缩边 e=uv使得 G-{u,v}仍然是k连通的.结合以上两个结果,我们证明以下结论,同时给出图例说明最小度条件是必须的.　　 结论1设G是不含三角形的k连通图,k≥2,如果δ(G)≥k+1,那么G中有一条边e使得 G-V(e)仍是k连通的.　　 对于k连通图中的可去边,Holton等[39]首先给出了3连通图中可去边的定义.后来尹建华在1999年定义了4连通图可去边的概念[93].最近厦门大学徐丽琼在她的博士毕业论文[91]中把3连通图和4连通图的可去边的概念推广到k连通图.设e是k连通图G的一条边,Gθ e表示图G做下列运算所得的图:(1)从G中去掉e得图G-e；(2)如果e的某个端点在G-e中度数为k一1,则去掉此端点,再两两连接此端点在G-e中的k-1个邻点；(3)如果经过(2)中的运算后,有重边出现,则用单边代替它们,使得此图为简单图.如果 Gθ e仍为k连通图,则称e为G的可去边.G的所有可去边的集合记为En(G).早在1969年,类似于3连通图中的可收缩边的结果,Barnette等[12]证明了每个阶大于4的3连通图必有可去边,并且给出了3连通图的一个递归构造方法.这是关于可去边的最早成果.尹建华[93]证明了4连通图 G不存在可去边的充要条件是 G是C52或 C62,并利用这个结果和4可收缩边的性质给出4连通图的一个递归构造方法,他的方法比Slater[71]的构造方法简单很多.徐丽琼等[91][92]给出了k连通图中可去边的定义后,证明了不同构于 K6的5连通图中必有可去边.另外对不含可去边的k连通图作了如下猜想:对于k(k≥3)连通图G,G中不存在可去边当且仅当k为奇数时,G≌Kk+1；当k为偶数时,G≌Kk+1或H(k+2)/2,后来这个猜想被苏健基等证实[76].至此k连通图中的可去边的存在性问题得到圆满解决.同时可去边在特殊子图结构上的分布问题也被广泛研究,本文关于可去边的结果就集中于此.　　 第三章主要研究了3连通图中可去边的分布.苏健基[72]证明了3连通图的哈密顿圈上的可去边数依赖于图中极大半轮的个数.我们把这个结果推广到3连通图的最长圈上.吴吉昌等[43][88]证明3连通3正则图的支撑树上或者支撑树外至少有2条可去边.我们把这个结果推广到不含极大半轮的3连通图中.同时我们利用3连通图可去边的性质证明了Thomassen在1976年提出的猜想(3连通图的最长圈上有弦.)对两类图是成立的,并给出图例说明这个结论没有被之前的结果覆盖.该章的结果列举如下:　　 结论2设G是阶大于5的3连通图并且G不是轮,C是G的最长圈,则(1)如果C不通过任何极大半轮,那么C上至少有3条可去边；　　 (2)如果 C仅通过一个极大半轮,那么C上至少有2条可去边；　　 (3)如果C仅通过两个极大半轮,那么C上至少有1条可去边.　　 结论3设G是没有极大半轮的3连通图,那么G的支撑树上或支撑树外至少有2条可去边.　　 结论4设G是3连通图且｜G｜≥6,C是图G上的最长圈,如果｜E(C)∩ER(G)｜≤5,则 C上有弦.　　 结论5设 G是3连通图且｜G｜≥9,C是图G的最长圈,如果｜(E(G)-E(C))∩ER(G)｜≤7而且G中任意的原子都跟C有交点,则C上有弦.　　 第四章主要研究了5连通图中可去边的分布.徐丽琼在给出5连通图的可去边的定义后讨论了它的分布情况,并证明了[91]对于5连通图G,如果最小度至少是6或围长至少是4或G中不含原子,那么G中任意的圈C至少有两条可去边；如果最小度至少是6或围长至少是4,那么G中任意的支撑树T上至少有两条可去边.我们推广了上述结果.　　 结论6设G是阶大于7的5连通图,那么G上任意的三角形上有1条可去边.　　 结论7设G是阶大于9的5连通图,C是G的一个圈,那么(1)如果C与任何原子都是点不交的,则C上有2条可去边；　　 (2)如果C仅与一个原子有交点,则C上有1条可去边；　　 (3)如果G中不含原子且C是哈密顿圈,则C至少有3条可去边；　　 (4)如果G中每对相邻的点对x,y都有d(x)+d(y)≥11成立,则C上有2条可去边.　　 结论8设G是阶大于9的5连通图,T是G的支撑树,如果G不含原子,则T上有2条可去边.　　 论文的最后一部分是关于图的棱可圈性.图G的棱是指G与完全图K2的笛卡尔积,记作 G□K2.如果 G□K2是哈密顿的,那么称图G是棱哈密顿的.对于图G的非空顶点子集 S,若G中存在一个圈经过S的所有顶点,那么称S是可圈的；若 G□K2中存在一个圈经过S以及它的拷贝S中所有的顶点,那么称 S是棱可圈的.图的哈密顿圈问题是图论中的一个经典问题.自1857年Hamilton正式引入这个概念以来已有大量的定理、猜想、综述.最近一个研究趋势是寻找哈密顿圈的变形来衡量图距离哈密顿性“有多近”,图的棱哈密顿性就是其中之一.最近,Ozeki[65]首次研究了图具有棱哈密顿性的度和条件,证明了对阶n≥2的连通图G,如果σ3(G)≥n,那么G是棱哈密顿的.同时他们给出实例说明所得的界是最好的.我们把这个结果推广到特定子集上,另外我们还讨论了无爪图的情形.　　 结论9设G是连通图且它的阶n≥2,φ≠S V(G),S是1G连通的.如果σ3(S)≥n,那么S在G□K2是棱可圈的.　　 结论10设图G的阶n≥2,S为G的顶点子集,且S≠φ,同时满足如下条件:　　 (ⅰ)S是1G连通的,(ⅱ)S∪N(S)中所有的顶点都不是爪的中心,(ⅲ)σ(S)≥n-3(图G中考虑).　　 那么 S在 G□K2中是棱可圈的或者 S是(a,b,c)-结构子图.