非固定步长的无向循环图的支撑树数

图的支撑树数是图的重要的不变量,也是网络可靠性的重要量度.循环图是一个重要的图类,可应用于局域网和分布系统的设计中.对有固定步长的循环图,其支撑树数已得到了研究.本文考虑有非固定步长的无向循环图Cpn(a1,a2-,…,ak,q1n,q2n,…,qmn),这里a1,a2,…,ak,q2,q2,…,qm,n和p都是正整数,a1≤a2≤…≤ak≤n/2,q1≤q2≤…≤qm≤p/2,且n是可变化的,因而有些步长并非固定.给出其支撑树数的一个公式,并得到其渐近性态和常数系数的线性递归关系.     

星网络的最优边容错图的结构

若图Ｇ中去掉任何Ｋ条边后所得的图含有生成了图同构于Ｇ０，则称Ｇ关于Ｇ０是Ｋ边容错图，记为Ｋ－ＥＦＴ（Ｇ０）图且边数尽可能小，则称Ｇ为最优Ｋ－ＥＦＴ（Ｇ０）图，设Ｓｎ表示ｎ点星，若一个最优Ｋ－ＥＦＴ（Ｓｎ）图的最大度尽可能小，则称为（Ｋ，ｎ）一极图，本文对于所有的Ｋ和ｎ，表征了最优Ｋ－ＥＦＴ（Ｓｎ）图和（ｋ，ｎ）－极图的结构。     

关于图的边容错的注记

F·Harary 和 J·Hayes 引入了如下的图的边容错的概念:图 G称为关于图 G 是k一边容错的,如果从 G 中移去任意 k 条边所得的每个图都含有图 G。本文得到了关于路,乘积图,有向路及有向圈的边容错的一些结果。     

几乎紧优双环网的无限族和常数步最优路由算法

得到了含两个参数a和b的紧优和几乎紧优双环网的无限族,其结点数n（a,b;e）和步长s（a,b;e）均为e的二次多项式,并给出它们的常数步最优路由算法,确切地说,至多只要4次算术运算或比较即可得到网络中的源结点0到任一结点的最短路。     

矩阵—树定理的一个简单证明

本文不用行列式计算中的Ｂｉｎｅｔ－Ｃｈａｃｈｙ定理,给出矩阵－树定理的一个简单证明。     

奇异k-紧整数无限族

设n，s1，s2是3个正整数，使得s1〈s2〈n，gcd（n，s1，s2）=1．双环网G（n；s1，s2）是个有向图，其结点集为V={0，1，2，…，n-1}，其弧集为A={i→i＋s1 （mod n），i→i＋s2（mod n）｜i∈V}，s1和s2称为步长．设d（n；s1，s2）为双环网G（n；s1，s2）的直径．令 d（n）=min{d（n；s1，s2）｜s1〈s2〈n}，d1（n）=min{d（n；1，s）｜1〈s〈n）． 已知d1（n）≥d（n）≥｜√3n｜-2=lb（n）．若d（n；s1，s2）=d（n）=lb（n）＋k（k≥0），则称G（n：s1，s2）是个k-紧优的双环网．虽然等式d1（n）=d（n）对于无限多个整数n成立，但也存在无限多个整数n使得d1（n）〉d（n），这样的n称为奇异整数．若d1（n）〉d（n）=lb（n）十k，k≥0，则这样的n称为奇异k-紧整数． 本文给出构造奇异k-紧整数无限族的方法，并对于k=1,2．…．20，构造出这样的无限族．     

k-ary n立方体中的测地泛圈

文中用归纳假设法证明了结论：当n≥2,k≥3,u和v是Qkn中任意2个顶点,由对称性,不妨设u=（0,0,…,0）,v=（d1,d2,…,dn）,这里0≤di≤k/2,（i=1,…,n）,记d=d1＋d2＋…＋dn≤1,N=kn,则对于每个偶数l适合2d＋2≤l≤N,则Qkn中有过u和v长为l的圈C,且C上u和v的距离为d.若有i和j满足1≤i≤j≤n,使得di≥1且dj≥1,或有且dj=k/2且dj=0,j≠i,1≤j≤n,则又有l=2d;当n≥2,k≥3是奇数,u和v是Qkn中任意2个顶点,由对称性,不妨设u=（0,0,…,0）,v=（d1,d2,…,dn）,这里0≤di≤k/2,,（i=1,…,n）,记d=d1＋d2＋…＋dn≥1,N=kn,r=max{di},则对于每个奇数l适合2d＋k-2r≤l≤N,则Qkn中有过u和v长为l的圈C,且C上u和v的距离为d.     

一族新的泛圈图

设Ｇ是ｎ阶２－连通图，任给ｕ∈Ｖ（Ｇ），Ｎ２（ｕ）是空集或Ｇ「Ｎ２（ｕ）」是完全子图，本文证明了：（１）若ｎ≥６，则Ｇ是泛圈图，（２）设（ａ，ｂ）不是Ｇ的２点割集，则Ｇ中存在以ａ和ｂ为二端点的Ｈａｍｉｌｔｏｎ路。