扇图与轮图的边平均Wiener指标及其算法

文章证明了扇图Fn和轮图Wn的边平均Wiener指标,并给出扇图中任意两边之间的平均距离的算法程序.     

基于迷宫算法思想的梯形图向AOV图的转换

PLC梯形图语言向AOV图的转换过程中,各顶点的直接前驱元件和直接后继元件的确定最为关键也最为复杂。利用迷宫算法思想来实现AOV图顶点的直接前驱和直接后继顶点扫描。首先从AOV图顶点集合中选出一个元件,并判断顶点的类型,然后利用迷宫算法思想对各种类型顶点进行相应的扫描处理。实例表明,此策略能快速准确地实现梯形图向AOV图的转换;算法直观易懂,实用性及通用性良好。     

单圈图的k-距离匹配控制数

单圈图是边数等于顶点数的连通图.令G=(V,E)是无孤立顶点的图,若集合DV(G)是G的一个k-距离控制集且导出子图〈D〉有完美匹配,则称D是G的一个k-距离匹配控制集.k-距离匹配控制数γkp(G)是G的最小k-距离匹配控制集的势.主要证明了单圈图k-距离匹配控制数的一个重要引理,由此找到了单圈图k-距离匹配控制数的上界,并构造了极图.     

按Laplace谱半径对一些偶单圈图的排序

研究一些偶单圈图按其Laplace谱半径排序的问题.利用扩圈变换对偶单圈图S1k的Laplace谱半径影响的证明方法,得出了顶点数为k+2,圈长为k(k≥10)的偶单圈图C(k+2,k)按其Laplace谱半径从大到小的顺序依次排在前三位和最后一位的单圈图.     

不含3,4圈的平面图的无圈边染色的一个结果

利用差值转移方法研究了不含3圈,4圈的平面图的无圈边染色,证得了它们的无圈边色数不超过Δ(G)+2。     

图C~2_n的优美性

给出了图C2n的定义,并对其优美标号进行研究,得到了当n=4k(k≥2)时图C2n是优美图的结论。     

A new class of antimagic join graphs

A labeling/of a graph G is a bijection from its edge set E(G) to the set {1,2,…,|E(G)|},which is antimagic if for any distinct vertices x anAy,the sum of the labels on edges incident to x is different from the sum of the labels on edges incident to y.A graph G is antimagic if G has an f which is antimagic.Hartsfield and Ringel conjectured in 1990 that every connected graph other than K_2 is antimagic.In this paper,we show that if G_1 is an m-vertex graph with maximum degree at most 6r+l,and G_2 is an n-vertex(2r)-regular graph(m≥n≥3),then the join graph G_1 v G_2 is antimagic.     

完全二部图K_(2,n)和K_(3,n)的一般点可区别全染色

借助已有的完全二部图K_(2,n)和K_(3,n)的点可区别IE-全色数的结论,利用组合分析及构造具体染色的方法探讨完全二部图K_(2,n)和K_(3,n)的一般点可区别全染色问题,确定了K_(2,n)和K_(3,n)的一般点可区别全色数.     

若干NP完全问题的特殊情形

讨论了图算法中若干ＮＰ完全问题在所给的图是一棵树时的特殊情形－ 利用树结构的前序编号表示法提出了解树的最大独立集问题、最小顶点覆盖问题和最小支配集问题的线性时间算法－在渐近意义下这些算法都是最优算法     

8个经典4色Ramsey数的新下界

提出了计算经典多色Ｒａｍｓｅｙ数Ｒ（ｑ１,ｑ２,…,ｑｎ）下界的一个算法,得到８个新的下界：Ｒ（３,３,３１１）≥３１４,Ｒ（３,３,３,１２）≥３５４,Ｒ（３,３,３,１３）≥４３２,Ｒ（３,３,３,１４）≥４６２,Ｒ（３,３,３,１５）≥,５２２,Ｒ（３,３,３,１６）≥６１８,Ｒ（３,３,３,１７）≥６７４,Ｒ（３,３,３,１８）≥７７０。