图的高阶限制边连通性

来源 :山西大学 | 被引量 : 2次 | 上传用户:lkcxm
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
令G=(V,E)是一个连通图.定义[A,B]为一端点在A中,另一端点在B中的边的集合.G的边割是指形为[U,(U)]的E(G)的子集,其中U是V(G)的非空子集,(U)=V(G)-U.设S(∈)E是G的一个边割,如果G-S的每个连通分支至少有k个顶点,那么称S是G的一个k-限制边割.若G存在k-限制边割,则称G为λk-连通图.称G的所有k-限制边割中所含边数最少的边割为G的λk-割,λk-割所含的边数称为G的k-限制边连通度,记为λk(G).令ξk(G)=min{|[X,(X)]|:|X|=k,G[X]是连通的}.若λk(G)=ξk(G),则称G是λk-最优的.2004年,Volkmann等提出了在邻域交条件下,图是λ-最优的.本文把这些结果推广到λk(G)-最优的情况.文章主要讨论了图在邻域交条件下的高阶限制边连通的最优性问题.  本文分为四章.第一章是预备知识,介绍了一些本文中将要用到的图论方面的基本概念和术语.  第二章简要介绍了限制边连通度的发展现状.  第三章给出了图G是λk-连通的邻域交条件.进一步,在某些条件下G是λk-最优的.主要结果如下:  (1)设k是一个正整数且G是一个阶不小于2k的图.若对于G中任意不相邻的顶点u,v都满足|N(u)∩ N(v)|≥k,则G是λk-连通的且λk(G)≤ξk(G).  (2)设k是一个不小于3的正整数且G是一个阶不小于2k的图.若对于G中任意不相邻的顶点u,v都满足|N(u)∩N(v)|≥k且ξk(G)≤(「)v/2」+k,则排除一类特殊图外(见第三章),G是λk-最优的.  (3)设k是一个不小于4的正整数且G是一个阶不小于2k的图.若对于G中任意不相邻的顶点u,v都满足|N(u)∩N(v)|≥k且ξk(G)≤(「)v/2」+k,则G是λk-最优的.  第四章给出了连通图G是λk-最优的充分性条件.主要结果如下:  (1)设k是一个不小于2的正整数且G是一个阶不小于2k的λk-连通图.设S=[X,Y]是G的一个满足|X|≥k+1与|Y|≥k+1的λk-割.如果对于G中任意不相邻的顶点u,v,当u,v都不在三角形中时满足|N(u)∩N(v)|≥k+1;当u和v中至少有一个在三角形中时满足|N(u)∩N(v)|≥2k-1,那么G[X]和G[Y]中分别存在一条k-路.  (2)设k是一个不小于2的正整数且G是一个阶不小于2k的图.如果对于G中任意不相邻的顶点u,v,当u,v都不在三角形中时满足|N(u)∩N(v)|≥k+1;当u,v至少有一个在三角形中时满足|N(u)∩N(v)|≥2k-1,那么G是λk-最优的.
其他文献
聚氨酯弹性体材料是制造轮胎胎面的理想材料。研究聚氨酯弹性体的物理性能及磨耗性能之间的关系对于研制性能优良的轮胎具有重要意义。 本文主要研究聚氨酯的物理性能与磨
与经典排队相比,休假排队是排队论中一个具有独立特色的方向,是一类更广泛、更复杂的排队系统.它主要解决在某些时间段内服务员无法服务顾客的情况,大量的实际问题均可以通过在
本文主要阐述了MOSFET(金属-氧化物-半导体场效应晶体管)中模拟电子输运的非平衡Green函数的数学理论。MOSFET是电路芯片的基本元件,当今微电子产品的极大丰富与迅猛发展是MOS
随着社会经济的发展,东西经济差异的增大,西部的许多农民都赶到了东部及沿海打工挣钱。在没有家长的监督下,一些学生根本就没学习这一念头,使得城市和农村学生的学习成绩差异
请下载后查看,本文暂不支持在线获取查看简介。 Please download to view, this article does not support online access to view profile.
期刊
可修系统的统计评定问题是可靠性理论中的重要组成部分。于丹等提出了一种贮存设备可修模型一一修如旧模型:维修后的设备相当于更换上一个同时贮存但没有失效的完全相同的设备
设M是n维完备的黎曼流形,它的截面曲率为正;令Vr和Ws分别是r维和s维的紧致全测地子流形.Pranlde在[1]中证明了,如果r+s≥n,那么Vr和Ws有非空交集。Frankle的证明方法是利用弧长变
在今天这个互联网时代,人们的通信越来越依赖于网络。而互联网是一个开放的网络,它对在其上传输的信息不提供安全性的保护。为了给传输信息提供保密性和完整性,IETFIPsec工作组
设半格E={e0>e1>…}∪{f0>f1>…}∪{0}。满足eiej=ej=ej(i≤j);fifj=fj(i≤j);eifj=0,则有Munn半群TE,称为双Cω-半群。我们对这类半群进行了分析和和讨论,得到了TE的元素形式TE={αij
历史学科在部分学生看来是副科,因此学习不认真。教师为了提高教学质量,开始以考为纲,其实这种做法也不尽有效。随着基础教育形势的发展,不仅要求我们要掌握新技术、新教法,