4-连通图中圈上的可去边和可收缩边

给出某些4 连通图中圈上的可收缩边和可去边的分布情况,得到如下结果:最小度至少为4或围长至少为5的4 连通图,其任一圈上至少有两条可去边;对4 连通图中的某些最长圈上至少有两条可收缩边.

6连通图中的可收缩边(英文)

Kriesell(2001年)猜想:如果k连通图中任意两个相邻顶点的度的和至少是25k/4-1,则图中有k-可收缩边.本文证明每一个收缩临界6连通图中有两个相邻的度为6的顶点,由此推出该猜想对k=6成立.

6连通图完美匹配上的可收缩边

采用分类讨论的方法,研究了6-连通图中可收缩边在完美匹配上的分布情况,得到了如下新结果.设G是阶大于12的6-连通图,M是G的一个完美匹配,若图G的任意断片的阶都大于3,则M上至少有2条可收缩边.

5连通图的可收缩边

给出５连通图包含可收缩边的一个条件。

无可收缩边的4-连通图的特征

本文证明了无可收缩边的4-连通图是两类特殊的4-正则图.这一结果推广了M.Fontet在[7]和[8]中的结论.

收缩临界5连通图中平凡不可收缩边的新下界(英文)

证明n个顶点的收缩临界5连通图中至少有n+1条平凡不可收缩边.

k-连通图的可收缩边(英文)

证明了对k-连通图G,若G的任意一个断片满足当N(F)中含有边就有|F|>k/4,则G至少有2条可收缩边.

n连通图的可收缩边

ｎ连通图的可收缩边，人们分别在图中无三角形及图Ｇ的最小度时等情况中，给出了边数下界，利用边断片给出了ｎ连通图在边原子阶≥ｎ／２时可收缩边的下界，进而给出在最小度时的边数下界．

5连通图的分裂和可收缩边

引入5连通图中度为5的顶点的分裂,利用分裂和收缩的运算对某类5连通图进行归纳,证明了对于阶至少为7的5连通图G,当G的任一断片的阶不等于2,且对G的任一5度顶点z,G[NG(z)]中含子图(K2∪2K1)+K1,则对G的任意顶点x,下列断言之一成立:1)x关联一条可收缩边;2)在NG(x)中存在一个5度顶点y关联一条可收缩边;3)在NG(x)中存在一个5度顶点y,使得对y作某一个分裂运算所得的图是5连通的.

极小k-连通图中的k-可收缩边

Ando证明了如果G是极小的k-连通图,且G中不含有K1+C4,若对于V(G)中的任意一个k度点x,与x关联的边中都存在一条不在三边形中的边,那么G中含有k-可收缩边.改进这个结果得出结论:如果G是极小的k-连通图,且不含图P,若G中任一k度点x,都存在与x关联的不在三边形中的边,那么G中有k-可收缩边.

h-连通图中可收缩边的存在定理

设 G是 h-连通的简单非完全图 ,对 G中的任一条边 uv,用 du,dv表示顶点 u、v的度 ,若 du + dv≥ 5 h/ 2 -1,则图 G存在可收缩边 ,从而推广了 Yoshimi Egam a[1 ]的结论 .

极大临界k-连通图的可收缩边

对极大临界k-连通图G的局部结构进行了讨论,证明了G中存在可收缩边e,使得G/e还是临界k-连通图.

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

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

5-连通图的可收缩边的分布

图的可收缩边问题对于研究图的结构和证明图的某些性质有着重要作用。本文给出了5-连通图中某些最长圈可收缩边的分布情况,用树型结构理论进行分类讨论,得到如下结论:不含2-断片的5-连通图的最长圈上至少有三条可收缩边。

最小度为3k/2-1(k为偶数)的k连通图的可收缩边

最小度δ（Ｇ）＝３ｋ／２－１（ｋ为偶数）的ｋ连通图Ｇ至少有｜Ｇ｜＋（５ｋ２－１０ｋ）／４条可收缩边，且当｜Ｇ｜是ｋ的整数倍时，这一下界是最好的．

一类k连通图的可收缩边（k≥2）

证明了｜Ｖ（Ｇ）｜≥３ｋ—１，δ（Ｇ）≥ｋ＋ｔ的ｋ连通图Ｇ若每条边至多含于２ｔ个三边形中，则Ｇ至少有条可收缩边（ｔ≥０）

5-连通图最长圈上可收缩边的分布

图可收缩边的存在性对于研究图的结构和证明图的归纳性质有着重要作用.该文对5-连通图中最长圈可收缩边的分布情况进行研究,证明了若G不包含某些特殊的2-断片,则最长圈C上至少包含六条可收缩边;进一步证明了若最长圈C中没有包含5度点的三边形则C至少包含两条可收缩边.

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

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

6-连通图的可收缩边

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

k-树图的收缩边

Narayanaswamy,Sadagopan和Sunil Chandran证明了k-树图G可收缩边数目的下界为V(G)+k-2,并指出这个界是紧的.该文给出了k-树图G可收缩边数目更一般的下界,由该文的结果可以推出Narayanaswamy等人的结果,进一步证明了可收缩边数目恰好为V(G)+k-2的图的特征.