共查询到10条相似文献,搜索用时 609 毫秒
1.
2.
给出了k-连通图中最长圈上的可收缩边的数目,得到如下结果:任意断片的阶至少为「k/2+1 的k-连通图中最长圈上至少有3 条可收缩边;更进一步,若该k-连通图中存在哈密顿圈,则哈密顿圈上至少有6 条可收缩边。 相似文献
3.
王兵 《吉首大学学报(自然科学版)》2008,29(1):10-12
借助Bauer定理给出了一个猜想的简短证明:如果图G含有k-因子且是2-连通的,并满足σ2(G)≥n-k,那么图G是哈密顿的. 相似文献
4.
恰含5条非基本边的极小3连通图 总被引:1,自引:0,他引:1
简单极小3连通图G中的一条不在任何三边形中的边e收缩之后所得到的图如果仍3连通,则称e为G的非基本边.Oxley与wu证明不是轮的简单极小3连通图至少包含3条非基本边,并且刻画了恰含3条或4条非基本边的不是轮的简单极小3连通图.现刻画恰含5条非基本边的不是轮的简单极小3连通图,它们是13类特殊的图. 相似文献
5.
我们给出一个猜想的简短证明:如果2-连通的图G含有k-因子,且满足σ2(G)≥n-k,图G是Hamiltonian的. 相似文献
6.
翟绍辉 《厦门理工学院学报》2010,18(1):18-20,23
设G是具有奇数个顶点的图,k是非负整数且满足V(G)≥2k+1,若G中任意一个k-匹配都可以扩充为G的一个几乎完美匹配,则称G是几乎k-可扩图.文中证明了连通的几乎1-可扩图与2-连通的几乎k-可扩二部图分别添加一个新边后仍保持原来的可扩性. 相似文献
7.
具有n个顶点的图G(n≥3)是k-可序哈密顿-连通的(k是整数,且2≤k≤n),如果对于G中每一个具有k个不同顶点的可序集合S={v1v2,…,vk},都存在G中的哈密顿路P包含S且不改变其中元素的次序.本文证明了:对于具有n个顶点的图G,u、v是G中任意两个不相邻的顶点,且d(u)+d(v)≥n+1.如果G是「k+1/2﹁-连通的k-可序图,k是整数且2≤k≤n/12,则G是k-可序哈密顿-连通图. 相似文献
8.
《广西师范学院学报(自然科学版)》2016,(4)
图可收缩边的存在性对于研究图的结构和证明图的归纳性质有着重要作用.该文对5-连通图中最长圈可收缩边的分布情况进行研究,证明了若G不包含某些特殊的2-断片,则最长圈C上至少包含六条可收缩边;进一步证明了若最长圈C中没有包含5度点的三边形则C至少包含两条可收缩边. 相似文献
9.
10.
郭知熠 《华中科技大学学报(自然科学版)》1985,(6)
本文定义了完全k-边可染子图的概念并证明:若图G无孤立点,且G中最大度数为k,则G中存在完全k-边可染子图。文中还定义了k孪生星形图的概念并证明;若连通图G中最大度数为k(k≥3),则G中存在完全(k-1)-边可染子图的充要条件是,G不是k孪生星形图。 相似文献