（v,e）——图正常2一着色的最大数目与极图

设Ｐ（Ｇ，λ）表示图Ｇ的色多项式。给定正整数ｖ，ｅ和λ，设ｆ（ｖ，ｅ，λ）＝ｍａｘ（Ｐ（Ｇ，λ），Ｇ是个（ｖ，ｅ）－ｌｔｕ ）。若一个（ｖ，ｅ）－图Ｇ使得Ｐ（Ｇ，λ）＝ｆ（ｖ，ｅ，λ），则称Ｇ是个λ－极图。本文指出文「２」给出的２－极图族是不完全的，并得到２－级图的完全族。     

一类双环网络的最优路由算法

设n＞h≥2.双环网络D(n,h)是如下定义的有向图其结点集是Zij={0,1,…,n-1},边集是E={i→i+1(modn),i→i+h(modn)0≤i≤n-1}.设n=qh+r,这里1≤r≤h-1,又设w=[(h-1)/(q+r)]≤h/r.本文提出了D(n,h)中源结点到目的结点的最短路径算法,该算法至多只要两次算术运算和一次比较,并且除了q,h,r和w外,各结点不必预先存储网络中别的信息.     

构造极小广播网络的新方法

广播是通信网络中信息传递的过程,在广播中,一个源结点的信息传递给网络中所有别的结点。这个概念在分布系统的控制中有着广泛的应用。本文考虑的广播有如下的约束条件:(1)每次呼叫仅包括两个结点;(2)每次呼叫需要一个单位时间;(3)在一个单位时间     

几族循环图的支撑树数

设Ｃｎ〈ａ１，ａ２，…，ａｋ〉是个循环图，ｔ（Ｇ）是图Ｇ的支撑树数。本文利用第二类Ｃｈｅｂｙｓｈｅｖ多项式给出了ｔ（Ｃｎ〈１，３〉，ｔ（Ｃｎ〈２，３〉），ｔ（Ｃｎ〈１，２，３〉），ｔ（Ｃｎ〈１，５〉），ｔ（Ｃｎ〈３，５〉），ｔ（Ｃ２ｎ〈１，２，ｎ〉）的公式。一个具体的例子表明，利用Ｃｈｅｂｙｓｈｅｖ多项式的性质，即使ｎ很大，这些公式的值是不难得到的。     

含参数的几乎紧优双环网的无限族

本文给出4类含有两个参数的几乎紧优双环网的无限族.     

关于广播函数B(2~k—2)和B(2~k—1)的值

广播是通讯网络中信息传递的过程,在广播中,一个源结点的信息传递给网络中所有别的结点,这个概念在分布系统的控制中有着广泛的应用,广播是通过在网络的通讯连线上置一系列的呼唤(信息传递)来实现的。本文考虑的广播具有如下的约束条件:(1)每次呼唤仅包括两个结点;(2)每次呼唤需要一个单位时间;(3)在一个单位时间里,任一个结点至多参与一     

含参数的k紧优双环网的无限族

本文得到了含参数的3紧优和4紧优双环网的无限族,其结点数形如n(e,m)=U(e) V(m),这里U(e)和V(m)都是2次多项式,e相对于m充分大.     

均衡Ramsey数

设G_1,…,G_t (t≥2)是单图,均衡Ramsey数B(G_1,…,G_t)定义为最小正整数n,使得对于每个N≥n和完全图K_N的每个均衡t一边染色K_N =H_1…H_t(均衡染色指H_i和H_j的边数之差至多为1,1≤i相似文献   

有根星的最优边容错

给定一个（有向）图Ｈ，称（有向）图Ｇ为关于Ｈ的ｋ－边容错图，记为ｋ－ＥＦＴ（Ｈ）图，若从Ｇ中移去任何ｋ条边所得的每个图都含有生成子图同构于Ｈ。Ｇ称为ｋ－ＥＦＴ（Ｈ）优图，若在所有ｋ－ＥＦＴ（Ｈ）图中，Ｇ的边数最小。Ｇ称为ｋ－ＥＦＴ（Ｈ）极图，若在所有ｋ－ＥＦＴ（Ｈ）优图中，Ｇ的点的最大度△（Ｇ）最小。设＾→Ｓｎ表示有根星，对于每个ｎ和ｋ，本文表征了ｋ－ＥＦＴ＾→（Ｓｎ）优图和极图。     

一族一致最可靠网络

n个结点e条边的简单图的集合记为Ω（n,e）。设奇数n≥5，e=n(n-1)/2-n 1/2,G的补图是P3∪n-3/2P2，则是G是Ω(n,e）中唯一的一致最可靠图。