[(n-1)/2]强n竞赛图的得分向量

n-竞赛图T_n称为k强的,如果T_n的任意一个由n+1-k个顶点导出的子竞赛图都是强的。 本文证明了下面的结果。设S=(s_1,s_2,…,s_n)是得分向量,n≥3,则S是隐含(n一1)/2]强n-竞赛图的当且仅当h(S)=[(n_1)/2],其中     

Kotzig有向图的度偶序列

1.引言 设T_n是n阶竞赛图,V={v_1,v_2,…,v_n}是T_n的顶点集合。设扩v∈V,T_n中所有被v占优的顶点个数s(v)是v在T_n中的得分,记s(v_i)=s_i,i=1,2,…,n.将v_1,v_2,…,v_n重新排列,使s_1≤s_2≤…≤s_n,则S=(s_1,s_2,…,s_n)即是T_n的得分向量。 在Bondy与Murty的名著《图论及其应用》一书的末尾处列举了50个图论中未解决的问题,其中第45问题是:刻划所有n-1阶子竞赛图都同构的n阶竞赛图。这个问题是Kotzig 1973年提出的(见[1])。作者、黄国勋与林毓材研究了这个问题。文献     

竞赛图的始终点集偶

本文引进竞赛图的始终点集偶的概念,证明了,每个n-竞赛图(n≥4)都具有始终点集偶,然后,应用这个结果证明了,每个强n-竞赛图(n≥4)都可扩张为2强(n 1)-竞赛图,最后,得到对于任意给定的得分向量是否存在以它为得分向量的2强竞赛图的一个判别准则。     

具有固定得分向量的竞赛矩阵的数目

本文考虑以允许平局的单循环比赛为模型的竞赛图（二重完全图）的定向图的邻接矩阵（竞赛矩阵）．给出了具有特殊得分向量的竞赛矩阵的数目,得到了具有ｎ阶强有效得分向量的竞赛矩阵的数目的下确界,并给出了达到此下界的得分向量的刻划．     

多部分竞赛图的Kotzig问题

§1.引言 1973年,A.Kotzig提出如下问题:刻划这样的n竞赛图T_n,使得所有删点子图T_(n-v)都同构(见[1])。在文[2]中,作者从n竞赛图的得分向量的角度,讨论了Kotzig问题。本文推广Kotzig问题到多部分竞赛图,即刻划这样的n_1×n_2x…×n_k k部分竞赛图T_(n_1,n_2,…,n_k,)使得所有删点子图T_(n_1,n_2,…,n_k,)-v都同构。这样的k部分竞赛图T_(n_1,n_2,…,n_k,)称为Kotzig的。     

独立集的度和与图的哈密尔顿性

关于哈密尔顿连通图的一个基本结果是Ore给出的：设G是n阶图,若对于任意两个不相邻顶点u和v,有d(u) d(v)≥n 1,则G是哈密尔顿连通的．设G是一个图,对于任意u (?)V(G),令N(U)=∪_(u∈∪)N(u),d(U)=|N(U)|,称d(U)是U的度．本文利用独立集的度和得到如下结果：设s和t是正整数,G是(2s 2t 1)-连通n阶图．若对于任两个强不交独立集S,T,|S|=s,|T|=t,有d(S) d(T)≥n 1．则G是哈密尔顿连通的．同时也得到图的哈密尔顿性的其它相关结果．两个独立集S和T称为强不交的,如果S∪T也是独立集．     

本原指数达到次大值的竞赛图的刻画

设n≥5,D为n阶强连通竞赛图,本文给出了本原指数达到次大值n 1的极图的完全刻画.     

κ-强竞赛图中外弧泛5顶点的数目

称具有n≥3个顶点的强竞赛图T中的一条弧是泛κ的,如果对所有的κ≤l≤n来说,它属于每个l-圈.本文证明了每个s-强(s≥4)竞赛图至少包含s+2个顶点使得它们的所有外弧都是泛5的.     

k-强竞赛图中外弧泛5顶点的数目

称具有n≥3个顶点的强竞赛图T中的一条弧是泛k的,如果对所有的k≤l≤n来说,它属于每个l-圈.本文证明了每个s-强(s≥4)竞赛图至少包含s+2个顶点使得它们的所有外弧都是泛5的.     

图类^－αKα,αUβCP（b）中的一类特殊整谱图

图G是一个简单，图G的补图记为^－G，如果G的谱完全由整数组成，就称G是整谱图，鸡尾酒会图CP（n）=K2n-nK2（K2n是完全图）和完全二部图Kα,α都是整谱图^[1]。^—μ1表示图类^－αKα,αUβCP（b）的一个主特征值，本文确图了当^-μ1=2b＋1时，图类中^－αKα,αUβCP（b）的所有的整谱图。     

图类■中的整谱图

设图G是一个简单图,图G的补图记为-G,如果G的谱都是整数,就称G是整谱图.鸡尾酒会图CP(n)=K2n-nK2(K2n是2n阶完全图)和完全图Ka都是整谱图[1].本文确定了图类■中的所有整谱图.     

一类新的泛圈图

本文所说的图都是简单无向图。未定义的术语和记号参见[2]。设 G=(V,E)的 n 阶图(n≥3),若 G 中含有 Hamilton 圈,则称 G 是 H-图。若G 中含有从3到 n 的所有长度的圈,则称 G 为泛圈图。如下两个定理是众所周知的。定理1 (Ore,1960)。若在 n 阶图 G 中,有uv(?)E(G)(?)d(u) d(v)≥n,则 G 是 H-图。     

图类￣(αKa∪βCP(b))中的整谱图

设图G是一个简单图,图G的补图记为(G),如果G的谱都是整数,就称G是整谱图.鸡尾酒会图CP(n)=K2n-nK2(K2n是2n阶完全图)和完全图Ka都是整谱图[1].本文确定了图类￣αKa∪βCP(b)中的所有整谱图.     

5阶图的结构完全正

1 简 介称n阶双非负矩阵,即非负半正定矩阵A为完全正的,如果A可分解为BBt,其中B是n×m的非负矩阵.或等价地,有n维非负向量β1,β2,…,βm使得A=β1β1t+…+βmβmt,B的可能最小的列数m称为A的分解指数（或A的CP秩）,记作 ψ（A）（或CPrankA）.记DPn为所有n阶双非负矩阵构成的集合;CPn为所有n阶完全正矩阵构成的集合.判断一个双非负矩阵是否为完全正以及确定它的分解指数是完全正矩阵研究的两个基本问题.对完全正矩阵的研究始于本世纪六十年代初,它的应用非常广泛,涉及组合设计     

关于Lanczos方法解对称方程组的一个判据

设A是n×n实对称非定矩阵,b是n维列向量,考虑方程组 Ax=b的求解问题。因为A是非定的,因此不能使用共轭斜量法,对于大型稀疏矩阵A的求解,文[1]和[2]提出使用Lanczos算法:取初始近似向量x_0,r_0=b—Ax_0,β_0=||r_0||z,令 q_1=r_0/β_0,逐次构造Lancoz序列q_1,q_2,…,q_(j 1),即     

n 阶临界3-边连通图的最大边数

本文中未经说明的术语和记号采自[2].设 G=(V,E)是一个简单图。G 的顶点数记作 n(G),边数记作 m(G),即 n(G)=|V|,m(G)=|E|.假设 G 是3-边连通图.G 的顶点 v(?)V 称为 G 的临界点,如果 G-v 不是3-边连通的;否则称为 G 的非临界点.如果每个 v(?)V 都是 G 临界点,则称 G 是临界3-边连通图.临界3-边连通图类记作 A,A_n 是 A 中所有 n 阶图的集合.假设 G(?)A,则对每个 v∈A,     

图类^-αKα∪βCP（b）中的整谱图

设图G是一个简单图,图G的补图记为^-G,如果G的谱都是整数,就称G是整谱图．鸡尾酒会图CP（n）=K2n-nK2（K2n是2n阶完全图）和完全图Kα都是整谱图．本文确定了图类^-αKα∪βCP（b）中的所有整谱图．     

无爪3 -正则图的独立数

如果图G的一个集合X中任两个点不相邻, 则称 X 为独立集合. 如果 N[X]=V(G), 则称X是一个控制集合. i(G)(β(G))分别表示所有极大独立集合的最小(最大)基数. γ(G)(Γ(G))表示所有极小控制集合的最小(最大)基数. 在这篇论文中, 作者证明如下结论: (1) 如果 G ∈R 且G 是n阶3 -正则图, 则 γ(G)= i(G), β(G)=n/3. (2) 每个n阶连通无爪3 -正则图 G, 如果 G(G≠ K₄) 且不含诱导子图K₄-e, 则 β(G) =n/3.     

(0,1)-矩阵类(?)(R,S)

我们把元素全部是1或0的矩阵称为(0,1)-矩阵。设A是一个m×n阶(0,1)-矩阵,其第ⅰ行全部元素之和为r_i(1≤i≤m),第j列全部元素之和为s_j(1≤j≤n)。那么称向量R=(r_1,r_2,…,r_m)为A的行和向量;S=(s_1,s_2,…,s_n)为A的列和向量。所谓具有行和向量R,列和向量S的(0,1)-矩阵类(R,S)是指:     

多部竞赛图中包含某条弧的圈

多部竞赛图或n部竞赛图是指一个完全n部无向图的定向图.2007年Volkmann证明了每个强连通的n部竞赛图(n≥3)至少存在一条弧它包含在从3到n的每个长度的圈中.在此基础上给出了强连通n部竞赛图中存在一条弧它包含在从3到n+1的每个长度的圈中的一个充分条件,并举例说明该条件在某种意义上的最佳可能性.