极图度的分布.pdf

第卷第期经济数学。
年月
极图度的分布‘
陈姜
浙江省杭州市,浙江教育学院数学系,
摘要图的围长是指中最短圈的长度若没有圈,则定义的围长为无究大本丈研究有。个顶板,
围长至少为十图的最大边数,记作。,,‘,· ,我们称这种国长至少为。,并具有录多边的
田为极图我们将讨论这种极图的一个重要性质,即极图度的分布
关盆词围长,极图,度
引言
我们将采用中的图论的基本符号,我们认为所有的图都是简单图,即其既无多重边又无
环图的顶点集和边集分别用和表示,顶点数和边数分别用和。表示,顶
点的最大度和最小度分别用乙和创表示图的度序列定义为,表示度,表示
度为的顶点个数,玉兰例如,图的咬。显然,若,则是一个正
则图我们把一个具有较小的值即。了石的图认为是一个近似的正则图图的
围长是指中最短圈的长度若没有圈,则定义的围长为无穷大用,丈,,⋯
表示所有顶点数为并且围长至少的图用亡,丈,,⋯,,表示在,丈,。,
⋯,。中图的最大边数在本篇文章中我们主要考虑属于,笼,的图,并简称它们为
极图而称属于,,,⋯,。中的图为围长之的极图围长为且具有最小的顶
点数的正则图称为一笼这些图在和改【〕证明笼的存在之后已经得到了深
入地研究笼通常很难找到,〔〕关于这个问题有一篇综述的文章
年,在【」中提到的值的确定问题,一个有个顶点并且围长至少为
的图的边数的最大值,他还猜测““目前最好的一个结果是见〔」
,
二岌一二刃厂上》二子· 在〔〕中,结合一和算法,利用计
了厄一份的一‘
算机生成具有个顶点以内的所有围长大于等于的图,这些图改进了的下限在【〕
中和讨论了围长之的极图的一些结构特征通常,构造极图是较难的,但
对于解决极图理论中高度对称图的研究及通信网络的设计中的一些难题却是非常有用见
【」在第二部分中,我们将讨论极图的一个重要特性
度序列
我们身边到处存在着对称我们看见许多自然形式表现的对称人的两边呈对称形,花的
收稿日期一一
经济数学第卷
各种各样的循环对称,贝壳上弯曲螺旋形对称,鱼鳞的平移对称对称在数学中也起着关键的
作用在图论中的最强的对称性是顶点传递性,相对较弱的对称性是正则性正则图是非常有
趣的一类图,人们通常能从它们中获得图的大量复杂及有趣的性质,如图,
图和图然而有时加上正则性后会产生一些意想不到的结果例如,当图是
连通平面图,并且每个面的边数最少有条边时见「」,哈密尔顿圈的存在问题仍为
问题但是和〔〕证明了几乎所有的正则图全存在哈密
尔顿圈
我们的兴趣集中在极图直观上,若一个图的度尽可能地均匀分布,则这个图很有可能成
为极图这一点导致我们去研究一个类似的问题—笼的构造在已知的,一笼中大部分是
极图,一笼是个顶点的图,,一笼是个顶点的图,,一笼中
的一个是个顶点的图,’和见〔〕发现了具有个顶点的,
笼,而,一笼是个顶点的一图至今尚未发现全的其他,一笼除
了,一笼和,笼,这些图均为极图,一笼边数是久为人知的在个顶点上极图的下
限见〕,」个顶点的极图具有条边,而不是,一笼中的条边,这个极图具
有度序列,。,显而易见,该极图的大多数顶点的度确实为,但它不是正则图这种
现象还出现在顶点上的个极图中见图,它们的度序列分别为,,,,,。和
,,,
图顶