临界二连通图的构造及有关极值问题

本文讨论了临界二连通图的一般性质,以及如何由一个图出发递归地构造出所有临界2连通图。最后讨论了临界二连通图中2次点的个数的下界以及极大边数等极值问题.     

一类极小k-连通图及一类正则连通图的构造

连通性问题是图论基本问题之一.关于2-连通图和3-连通图的构造已经令人满意地搞清楚了.但当 k≥4时,有关最小 k-连通图的结构,人们还知之甚少.本文给出了当 k≥4时的 k-连通图的构造,证明了所构图形为极小 k-连通图;另外还给出了一类 k-正则 k-连通图的构造,它是在顶点数相同时的最小 k-连通图.     

关于最大的极小k—连通图的构造

本文讨论了如何对已知的 k=k(G)构造一个 n 阶的具有最多边数的极小 k—连通图,同时得出了极小 k—连通图的边数的上界.如果 k 1相似文献   

两种特殊图类直径的上界

对边控制临界图与边控制极小图这两种特殊图类的直径进行了研究.给出了连通的kEDC(k≥3)图的直径的一个上界,并给出了4-EDC图的直径的一个更好的上界及3-EDC图的直径的可达上界.同时,利用控制点临界图的已有的结果以及一个图的直径与其线图的直径间的关系,直接给出了连通的k-EDM图的直径的一个上界,进而给出了3-EDM图和4-EDM图的直径的可达上界.     

F—图的最大边数

文献[2]求出了临界h-连通图中一个特殊图类—A-图的最大边数.本文推广了这一结果,使其适用于一个更广泛的图类—F-图.     

极小2—棱—连通图中自中图的一些性质

Buckley在文献[1]的定理3中证明了当边的数目m满足:n≤ m≤n(n-1)/2时自中心留存在.(这里n伏表图G的顶点数)本文从极小2一棱一连通图的构造出发,研究了极小2一棱连通图中自中心留的一些局部情况,并得出了它的一些性质.根据本文的结果,不仅可以构造一些自中心留类,而且也为构造更大范围内的中心图打下了一定基础.     

临界图性质的探讨

临界图是连通的第二类图,而且对于G的任意一条边e,G-e是第一类图。本文主要证明了满足一定条件的Δ=6的平面图不是临界的,并给出了临界图的一个性质.     

极小强连通有向图

强连通有向图D称为极小的,若在D中删去任意一条弧,则所得的有向图不是强连通的.讨论了极小强连通有向图的耳朵分解的一些性质,构造了非平面极小强连通有向图的例子, 证明了极小强连通图的点色数至多是3,并且当极小强连通图的耳朵分解中每个耳朵的长度不小于4时,它有两个不相交的准核.最后确定了给定顶点数的极小强连通有向图的弧数的界,刻画了相应的极图.     

极小3连通图的非基本边数

利用扇,断片及简约图的概念,得到不为轮的极小3连通图的非基本边数与其简约图的非基本边数相等,从而将求极小3连通图的非基本边数问题转化为求其简约图的非基本边数问题后,给出简约极小3连通图非基本边数的一个下界,刻画了达到下界的图类.     

极小2—连通图的圈数的上界

1967年G·A Dirac解决了极小2-连通图的构造问题。本文在此基础上,进一步分析了含圈最多的极小2-连通图,找出了它的特征,从而构造出含圈最多极小2-连通图—K_2,n-2,得到了极小2-连通图圈数的精确上界。     

恰含5条非基本边的极小3连通图

简单极小3连通图G中的一条不在任何三边形中的边e收缩之后所得到的图如果仍3连通,则称e为G的非基本边．Oxley与wu证明不是轮的简单极小3连通图至少包含3条非基本边,并且刻画了恰含3条或4条非基本边的不是轮的简单极小3连通图．现刻画恰含5条非基本边的不是轮的简单极小3连通图,它们是13类特殊的图．     

射影平面上外可平面图的最小圈基

研究了射影平面上2 连通图的圈基结构,并给出了在嵌入的边宽度ew(G)≥5时外可平面图的最小圈基结构,证明了最小圈基与最短不可收缩圈之间的一一对应性.     

6-连通图最长圈上的可收缩边

 图的可收缩边与可去边是研究连通图的构造和使用归纳法证明连通图一些性质的有力工具。设G是一个6-连通图,e∈E（G）,若收缩e后得到的图仍是6-连通的,则称e是G的可收缩边。采用树型结构理论进行分类讨论,得到如下结论：① 如果P:x=x1x2…xn=y是6-连通图G的一条最长（x,y）－路,xi xi+1是一条不可收缩边,且S={xi,xi+1,u1,u2,u3,u4}是其对应的6-点割,则G-S的每一个断片至少包含P上的一个点;② 设P:x=x1x2…xn=y是6-连通图G的一条最长（x,y）－路,且G的任意断片的阶都大于2。如果P上任意顶点xi都满足条件d（xi）≥7或者若d（xi）=6则[V（P）]中无3-圈包含它,那么P上至少包含一条可收缩边。在上述结论的基础上,进一步研究了任意断片阶都大于2的6-连通图中最长圈上的可收缩边的分布情况,得到如下新结果：任意断片阶都大于2的6-连通图最长圈上至少有两条可收缩边。     

P3——支配图哈密尔顿性的一个充分条件

在文献[4]中作为半无爪图的一个超类,作者引进P3-支配图,并研究了这类图一些性质。设G是2-连通的P3-支配图,我们证明了G是哈密尔顿的一个充分条件局部连通型条件。     

两类2连通(n,n+4)图的色唯一性

2连通的(n,n 4)图是有n个顶点n 4条边的连通图,利用图的色多项式理论研究了两类2连通的(n,n 4)图的色性,由此部分或完全解决了图G5和图G12的色唯一性问题.     

4连通图中可去边的一些性质

给出了4连通图中可去边的一些性质．利用4连通图的可去边,给出了4连通图的Kuratowski定理的一个较简单证明．     

某些5-连通图中最长圈上的可收缩边

给出某些5-连通图中某些最长圈上的可收缩边的分布情况,得到如下结果:某些5-连通图的某些最长圈上至少有两条可收缩边。     

收缩临界6-连通图中的6度点

每一个收缩临界6－连通图都有一个6度点。最近袁旭东证明了任何收缩临界6－连通图都存在两个相临的6度点。对于收缩临界6－连通图中的每一个点都存在一个6度点使得这两点相邻或距离为3，从而对收缩临界中6度点的分布有了更进一步认识。     

一类极大临界2连通图的结构

引入图的粘合的概念，讨论了极大临界2连通图G的性质，给出了一个图是这类图的一个充要条件。由此给出该类图的一种新的构造方法，即G能按条件先粘合一系阶大于2的完全图的边，然后粘合四圈C4的t个拷贝得到．     

6-连通图的可收缩边

讨论一类6-连通图的可收缩边的分布情况,得到可收缩边的数目的下界为1/4|V(G)|.