图的升分解问题的两个新结果

Ａｌａｖｉ等人在１９８７年定义了图的一种新分解,即“升分解”（ＡｓｃｅｎｄｉｎｇＳｕｂｇｒａｐｈＤｅｃｏｍｐｏｓｉｔｉｏｎ）,并且猜想：任意有正数条边的图都可升分解．该文证明了下面两个新结果：（１）Ｈｉ是ｉ条边的Ｋｎ的子图,当ｎ＋１≤ｉ≤２ｎ－２ｎ／３［］２－２时,Ｇ＝Ｋｎ－Ｈｉ可升分解为Ｋ１,１,Ｋ１,２,…,Ｋ１,ｎ－５,Ｋ１,ｎ－４,Ｇｎ－３（ｎ≥６）,其中Ｋ１,ｎ－４Ｇｎ－３．（２）Ｈｉ是ｉ条边的Ｋｎ的子图,当ｉ≥２ｎ－２ｎ／３［］２时,Ｇ＝Ｋｎ－Ｈｉ不一定有定理１形式的升分解．     

异步并行非线性多分裂Newton-GAOR方法的收敛性

本文首先给出了解非线性方程组的Ｎｅｗｔｏｎ－ＧＡＯＲ方法．在此基础上，我们得到了异步并行非线性多分裂Ｎｅｗｔｏｎ－ＧＡＯＲ（简记为ＡＰＮＭ－Ｎ－ＧＡＯＲ）方法，证明了方法的局部收敛性，给出了其Ｒ１收敛因子，并得出了多步ＡＰＮＭ－Ｎ－ＧＡＯＲ方法比一步方法收敛更快的结论，文［１］［４］可看作本文的特例     

X—可迹图的两个推论

在［２］中的结果：如果Ｇ是ｎ阶２－连通图，Ｘ∪→－Ｖ（Ｇ）并且ＮＣ２（Ｘ）≥ｎ－１／２，则Ｇ是Ｘ－可迹图。本文利用该结果推广了Ｄｉｒａｃ和Ｏ．Ｏｒｅ分别在文献［３］和［４］中有关可迹图方面的结论。     

论色式的一次项系数

引进了几个图之联合图的概念，在文［３］的基础上，继续讨论了色式的一次项系数，指出了当１１≤｜α＿１（Ｇ）｜≤２３时，图Ｇ所具有的结构。     

关于“k——序哈密尔顿图”一文的一点注记

本注记改正文［１］中一个引理的一点错误及引理证明中的失误。重新证明了若ｎ阶图Ｇ的任二不相邻顶点ｕ、ｖ有ｄ（ｕ）＋ｄ（ｖ）≥ｎ＋２ｋ－７，４≤ｋ≤ｎ，则对于Ｇ的任意不同的ｋ个顶点ｖ１，ｖ２，…，ｖｋ，有ｖ１（ｘ１）ｖ２（ｘ２）…ｖｋ－１（ｘｋ－１）ｖｋ型ｖ１—ｖｋ路（我们用ｖｉ（ｘｉ）ｖｉ＋１表示ｖｉｖｉ＋１或ｖｉｘｉｖｉ＋１。）或ｖｋｖ１（ｘ１）…（ｘｋ－２）ｖｋ－１型ｖｋ—ｖｋ－１路；若对任不相邻两顶点ｕ、ｖ有ｄ（ｕ）＋ｄ（ｖ）≥ｎ，则对于Ｇ中任三点ｖ１，ｖ２，ｖ３存在ｖ１（ｘ１）ｖ２（ｘ２）ｖ３型ｖ１—ｖ３路。最后对文［１］中的公开问题１提出自己的看法。     

路和回路的各种乘积图的联结数

图的联结数是图的示性数之一．Ｄ．Ｒ．Ｗｕｏｄａｌｌ［１］首先引进了这个概念，研究了联站数与 图的其它量之间的关系．Ｖ．Ｇ．Ｋａｎｅ，Ｓ．Ｐ．Ｍｏｈａｎｔｙ和Ｒ．Ｓ．Ｈａｌｅｓ［２］研究了一些乘积图 的联结数．［３］中证明了［２］中提出的关于ｂｉｎｄ（Ｃｍ×Ｃｎ）的猜想．本文进一步研究了［２］、［３］未 解决的若干乘积图的联结数，得到了Ｌｍ×Ｃｎ，Ｃｍ　Ｃｎ，Ｌｍ　Ｃｎ，Ｃｍ＊Ｃｎ，Ｌｍ＊Ｃｎ，Ｃｍ（Ｃｎ），Ｌｍ（Ｃｎ）等图的联结数。     

图的连通Domination数与若干不变量的联系

研究了图的连通控制数与全控制数、无赘数、点色数、点荫度等不变量之间的关系．将 文［２］中的一个结果ｒｃ（Ｇ）≤４ｉｒ（Ｇ）－２改进为ｒｃ（Ｇ）≤３ｉｒ（Ｇ）－２，且上界可达。     

亚正定矩阵的判定方法

中图分类号Ｏ１５１文［１］～［３］给出了亚正定矩阵的理论及有关性质,本文给出亚正定矩阵的一个判定方法．定理１［１］Ａ为ｎ阶实方阵,则下列诸结论等价：（１）Ａ亚正定．（２）Ａ＋Ａ′正定．（３）对任意实ｎ元非零列向量Ｘ,都有Ｘ′ＡＸ＞０．（４）Ａ可逆且Ａ...     

图两参数的关系及图的分类

本文讨论了与图的伴随多项式和匹配多项式密切相关的两类参数的关系,并刻画了匹配多项式参数Ｒｍ（Ｇ）＝１,０,－１,－２,－３的图簇。     

关于p阶临界h边连通图的一个注记

文［１－４］分别给出了ｐ阶临界２边连通图ｐ阶临界３边连通图以及ｐ阶临界ｈ（≥４）边连通图的最大边数及其结构。本文相应给出了ｐ阶临界ｈ（≥３）边连通图最大边数更为简捷的结果。可应用于改进和提高通讯网络的可靠性     

拉姆齐图R(4,5)的递阶生成

对于已知经典的拉姆齐数，其对应的拉姆齐图R(3，3)，R(3，4)R(3，5)，R(3，6)，R(3，7)，R(3，8)和R(3，9)均可递阶生成．给出了一个通过R(4，4)图递阶生成的一个R(4，5)拉姆齐图，证明了R(4，5)≥25．同时发现修改所构造的R(4，5)图的10条拉姆齐临界边，该图将变为经典10-正则的R(4，5)图．     

一类变换图的距离性质

求得一类变换图G(R*,S*)(其中R*=(r1,r2),S*=(1,…,1))的直径为r,证明了对于G(R*,S*)中任意2个距离为k的点,恰存在k2条内部不交的最短路联结这2个点,并且最多存在r1 n－r1〗条内部不交的路联结这2个点.     

UMT整环上的w-维数

设R是整环,X是R上的一个未定元,{Xλ}λ∈Λ是R上任意多个未定元的集合.证明了若R是UMT整环,则w-dimR=w-dim(R[{Xλ}λ∈Λ]).进一步研究了UMT整环上的群环,证明了若R是UMT整环,则w-dimR=w-dimR[X;G].     

关于二分图的F-Hamilton性

设G是一个简单图,任意e∈E（G）,定义e=uv在G中的度d（e）=d（u）＋d（v）,其中d（u）和d（v）分别为顶点u和v在G中的度数。设F是二分图G的一个1-因子,如果G中有包含F的Hamilton圈,则称G是F-Hamilton的;给出了二分图是凡Hamilton的一个新的充分条件。     

关于Hamilton图的充分必要条件

引入与图Ｇ具有相同连通性的图Ｇ的相关简单图ＧＲ的概念,并通过对ＧＮ的邻接矩阵的恒式的研究,给出了任意图Ｇ是Ｈａｍｉｌｔｏｎ图的充分必要条件,得到了以下主要结论：定理：图Ｇ是Ｈａｍｉｌｔｏｎ图的充分必要条件,是图Ｇ的相关简单图ＧＲ的邻接矩阵的恒式ＰｅｒＧＲ不为０。     

E^4和E^5中的超球面的特征

本文讨论了E~(n+1)(n=3,4)中的超球面的特征,推出了一些新的结果(定理1和定理2);最后一个结果改进了A.Svec的一个定理.     

3正则3连通图的转发指数

n阶连通图G的路由选择R是由连接G的每个有向顶点对的n(n-1)条路组成.R经过G的每个顶点(每条边)的路的最大条数称为G关于R的点转发指数ξ(G,R)(边转发指数π(G,R)).对G的所有路由选择R,ξ(G,R)(π(G,R))的最小值称为G的点转发指数ξ(G)(边转发指数π(G)).对于k正则k连通图G, Fernandez de la Vega和Manoussakis [Discrete Applied Mathematics, 1989, 23(2):103-123]证明ξ(G)≤(n-1)·[(n-k-1)/k]和π(G)≤n[(n-k-1)/k],并且猜想ξ(G)≤[(n-k)(n-k-1)/k].我们分别改进了ξ(G)≤(n-1)[(n-k-1)/k]-(n-k-1)和π(G)≤n[(n-k-1)/k]-(n-k),并且证明了猜想对k=3的情形.     

具有给定得分向量的竞赛图类的对换图的连通度

本文证明:对具有给定得分向量R的竞赛图类T(R)的对换图G(R),若G(R)至少含有三个点,且G(R)不是一个长为4的圈,则G(R)为3—连通图。这个结果加强了Brualdi和李乔在文献[1]中关于竞赛图类的对换图的2—连通的结果。     

图的离心率值列的研究（英文）

设G为一个图,对任意x∈V（G）,其离心率e(x)定义为e(x)=max{d(x,u)│任意u∈（V（G）}。将G中各点的离心率的值按照（不重复）从小到大排列而得到的数列称为G的离心率值列。现设{ei}1 ≤i≤s为一个非减的整数数列。本得到了下面三个结果：（i){ei}1 ≤i≤s是图的离心率值列当且仅当{ei}1≤i≤s=[e1,es]且e1≥1,es≤2e1;（ii）定义NG（e)={x│x∈V（G）且e(x)=e},若│NG（e)│=1则e=r(G);(iii)有给定离心率值列[r,r s]的图的最小阶f[r,r s]为f[r,r s]={2r s,若0≤s≤r-2;r s 1,若s=r-1或r;这里,[s,s k]表示[r,r s]数列{r-1 i}1≤i≤s 1。