可靠通讯网络的构造

在可靠通讯网络的构造方面,F.Harary于1962年证明了“图Hm,n是m—连通的”的定理。此定理告诉我们,Hm,n是具有几个顶点,边数最少的m—连通图。 本文首先给出了连通正则图是m—连通的的充要条件,然后利用这一结果及循环图的性质,推广了“图Hm,n是m—连通的”这一定理,并构造出包含Hm,n在内的具有n个顶点、边数最少的一类m—连通图。最后利用同构的循环图构造出一类可靠通讯网络。     

3r阶循环群的最小图

设α(n)是自同构群与n阶循环群C(n)同构的图的最小顶点数,该文构造出群为C(3r)的具有α(3r)个顶点的边数最少的图,并证明了这样的图是唯一的.     

（k，k-1）-双正则图的平衡Judicious Partitions

Bollobás和Scott提出猜想:任意一个边数为m且最小度大于1的图存在顶点集的平衡二部划分使得每一部分点集的导出子图包含的边数不超过m/3.Bollobds和Scott证明了绝大部分正则图存在顶点集的平衡二部划分使得每一部分点集的导出子图包含的边数比m/4小.这里讨论(k,k-1)-双正则图的平衡二部划分,证明了每一个(k,k-1).双正则图存在平衡二部划分使得每一部分点集的导出子图包含的边数是m/4左右.     

无三角形3-正则图的几个参数的界

图G的一条边称为割边是指删去该边后,使得余下的图的连通分支数增加。图G 中的一个两两不相邻的边子集称为图G 的一个匹配。图G 的一个最大匹配的边数称为图G 的匹配数。图G 中的一个与G 的每个团都有交的顶点子集称为G 的一个团横贯集,图G 中元素个数最少的团横贯集的顶点数称为G 的团横贯数。本文针对n阶连通无三角形的3-正则图G=(V(G),E(G)),首先给出了其割边数的一个上界(n-10)/4;其次对它的匹配数得到了一个下界(11n-2)/24;再次对它的线图的团横贯数呈现了一个上界(13|E(G)|+3)/36。同时刻画了达到这些界的极值图。
     

完全图并的连续性

给图G的每条边e都赋一个权w(e),所得的赋权图记为G(w).在G(w)中,顶点v的标号f(v)等于与顶点v相邻各边的权之和,当各顶点标号相异时,称G(w)是非正则的.G(w)的非正则和是在所有以图G为基础图的非正则图中,各顶点标号的和为最小时的值,记为∑(G).若非正则和∑(G)=nδ 2n,则称图G连续.利用图的权矩阵,讨论了图nK4m、nK5m、nK6m和nK7m的连续性.     

与图Zeta函数相关的一个函数的导数值

设G是含有n个顶点和ε条边的图,G的Zeta函数可以表示为ZG(u)=(1-u2)n-ε/f(u),其中f(u)=det(I-uA (G)+u2(D (G)-I)),A(G)与D (G)分别表示G的邻接矩阵与度对角矩阵。分别利用正则图的TU子图的权重ω和二部图的顶点n和边数ε来表示相应的f′(-1)的值。     

正则图的Balaban指标

连通图的Balaban指标(也叫J指标)的定义是m1J(G)=m-n+2uv∑∈E(G)σG(u)σG(v)其中m,n分别是图G的边数和点数,σG(u)表示在G中从顶点u到其它各个顶点的距离之和.Balaban指标被广泛应用于各种QSAR和QSPR的研究.首先给出连通3-正则图的Balaban指标的一个上界.然后对KNOR M等人介绍的两类3-正则图,分别给出它们的Balaban指标计算公式和上界,改进了KNOR M等人的结果.     

无三角形3-正则图的几个参数的界

图G的一条边称为割边是指删去该边后,使得余下的图的连通分支数增加。图G中的一个两两不相邻的边子集称为图G的一个匹配。图G的一个最大匹配的边数称为图G的匹配数。图G中的一个与G的每个团都有交的顶点子集称为G的一个团横贯集,图G中元素个数最少的团横贯集的顶点数称为G的团横贯数。本文针对n阶连通无三角形的3一正则图G-（V（G）,E（G））,首先给出了其割边数的一个上界（n—l0）／4;其次对它的匹配数得到了一个下界（11n-2）／24;再次对它的线图的团横贯数呈现了一个上界（13｜E（G）｜＋3）／36。同时刻画了达到这些界的极值图。     

某些整循环图的能量

给出了整循环图的一个分解定理,利用这个分解定理得出了一些整循环图的能量,相应地决定了其超能性.此外,还构造了几族具有n个顶点不同谱的正则等能超能图.     

具有k个悬挂点的双圈图的Harary指数

双圈图是指顶点数等于边数减1的连通图,Harary指数是指图中所有顶点对的距离倒数之和.基于此,主要研究了具有k个悬挂点且两个圈只有一个交点的n阶双圈图有极大Harary指数的图类.     

逼近4正则图的最小顶点覆盖问题的难解性(英文)

证明了逼近4正则图的最小顶点覆盖问题在某个常数因子内是计算难解的.相似地,对于5正则图、6正则图等的最小顶点覆盖问题,这个结论也成立.已知逼近3正则图的最小顶点覆盖问题在某个常数因子内是计算难解的,文章扩展了这个结果到4正则图情况,用K-归约证明这个结果,给出了一个从3正则图的最小顶点覆盖问题到4正则图的最小顶点覆盖问题的K-归约.     

折叠交叉超立方体的2-额外连通度和2-额外边连通度

有各种各样的方法去衡量不同网络的可靠性和容错性.一个连通图G的g-额外连通度Kg(g-额外边连通度λg)是顶点数最小的顶点集S(边数最少的边集S),使得G-S不连通,并且剩下的每个连通分支含有的顶点数至少是g+1.探究n-维折叠交叉超立方体FCQn的2-额外连通度和2-额外边连通度,证明得到如下结论:当n≥8时,κ2(...     

拟轮图的导出匹配可扩性

从导出匹配可扩图的定义、结构出发,研究了拟轮图的性质, 构造了一类新的导出匹配可扩图Γn. 主要结果如下:(1)判定具有奇数个顶点的图几乎导出匹配可扩性是co-NP-完全的. (2)Γn中的任何一个图均是边数为5n-6的导出匹配可扩的拟轮图.     

奇围长(2t 1)的最小正则图

本文研究了奇围长(2~t 1) 的k-正则图的最少顶点数和极图。     

给定控制数的连通二部图的最大边数

研究了n个顶点的连通二部图当控制数γ(G)≥3,最大度Δ(G)≥n-γ(G)-1时的最大边数。     

序列图的一些必要条件与非序列图类

为纠错码问题提供理论基础，在运用同余、奇偶性方法的基础上，给出了用点边二种观点分析边标号的方法。使用这种方法，得到了一般序列图、正则序列图、Euler序列图、圈的粘接序列图和圈的并序列图的必要条件，证明了边数为2k，k是奇数的Euler图是非序列图类，讨论了m个n圈的粘接图中的非序列图类：分析偶圈的特征，构造了偶圈的具有同顶点集的序列母图并给出其序列标号表达式。这些结果在通讯、军事等领域有重要应用价值。     

正则图Cartesian积的线图的秩

设G是一个顶点为n,度为r的正则图,那么它的边为m=1/2nr.G线图是顶点为m,度为（2r-2）,边为1/2nr（r-1）的正则图,本文研究两个正则图或强正则图的Cartesian积图的线图的秩,得到了许多结果,推广了G．J．Davis,G．S．Domke等人的结论．     

有限制条件的单台机器的排序问题

根据给定n个工件在一台机器上加工时工件间的先后关系 ,定义了一个n个顶点的有向图D ,简化图D得排序图D ,通过穷举图D 的顶点的拓扑序列 ,搜索出了n个工件完工时间之和最小、机器加工完n个工件总时间最少和延误损失最少的加工顺序 .     

具有最大能量的直径为6的毛毛虫树

研究具有最大能量的直径为6的毛毛虫树的能量问题.给出毛毛虫树的定义,并介绍了直径为6的毛毛虫树;通过比较不同变换下毛毛虫树的能量大小,得到各悬挂边数目之间的关系;给出n取不同值时,有最大能量的直径为6的毛毛虫树的一些结论,解决了给定顶点数和边数的连通图中具有最大能量的图的问题.     

具有最小匹配能量的广义仙人掌图

为了研究具有最小匹配能量的广义仙人掌图的结构,利用一些图形变换对图的匹配能量产生影响的相关方法,得到了具有最小匹配能量的广义仙人掌图的结构:在所有顶点数、边数、块为圈的数目和块为双圈图的数目都固定的广义仙人掌图中,G﹡(n,m,r,s)是匹配能量最小的图;在所有顶点数和边数都固定的广义仙人掌图中,G﹡(n,m,1,(m-n)/2)或G﹡(n,m,0,(m-n+1)/2)是匹配能量最小的图。