整数偶序列为蕴含强连通的Beineke－Harary判准

一个由ｎ个非负整数有序对构造的序列是有向可图的,如果它是某个有向图的度序列．一个有向可图序列是蕴含强连通的,如果它是某个强连通有向图的度序列．Ｂｅｉｎｅｋｅ和Ｈａｒａｒｙ给出了一个有向可图序列为蕴含强连通的判准．Ｂｅｉｎｅｋｅ－Ｈａｒａｒｙ判准的充分性证明是“相当长”的（见［１］）．本文的目的是给出Ｂｅｉｎｅｋｅ－Ｈａｒａｒｙ判准的充分性的一个简短证明．     

图的度序列

图的度序列是图论研究中一个重要的课题．至今已发表了４００余篇文章．本文概述这一课题的某些进展，其中包括了可图序列的判准、蕴含Ｐ可图序列和强迫Ｐ可图序列的一些主要结论，同时列出了一些有待进一步研究的问题．     

蕴含W6-可图序列

摘要对于给定的图日,如果可图序列π有一个实现包含日作为子图,则称丌是蕴含H-可图的．本文给出了可图序列π蕴含W6-可图的一个充分条件,其中Wτ是τ个顶点的轮图．     

有向图超级弧连通的充分条件

如果有向图D的任一最小弧割都是发向某个度为δ的顶点的弧集或者是由某个度为δ的顶点发出的弧集,则称有向图D是超级弧连通的,给出了有向图超级弧连通的一些充分条件.     

蕴含W_6-可图序列

对于给定的图H,如果可图序列π有一个实现包含H作为子图,则称π是蕴含H-可图的.本文给出了可图序列π蕴含W_6-可图的一个充分条件,其中W_r是r个顶点的轮图.     

依赖团数的有向图极大与超级边连通的度序列条件

互连网络通常以有向图为模型,有向图的弧连通度是网络可靠性的一个重要参数.给出了依赖团数的有向图极大和超级边连通的度序列条件.     

定向可图的度偶序列

n为非负整数序列，若存在以该序列为度序列的图，则称n为可图的，特别的，若此图是一个定向图，该序列则称为是定向可图的，本提出了一个判断序列是否为定向可图的充分必要条件，并且在定理的证明过程中给出了一个在定理条件下构造所求定向图的有效算法。     

有向图的拟强连通和超拟强连通性

Geller,F.和Harary,F.在文献[2]中对有向图的强连通,单侧连通和弱连通给出了几个性质定理。Berge,C.在[3]中曾定义了有向图的拟强连通。并对拟强连通与有向树的关系等给出了两个定理。本文对有向图的拟强连通和超拟强连通性得到了与[2]中相应的结果。     

多部竞赛图的κ边连通性及其得分序列

对于有向图，熟知有三种ｋ边连通性，本文首先证明这些ｋ边连通性是等阶的。其次，利用多部竞赛图的得分序列，我们给出了多部竞赛图为ｋ边连通的一个简便的判定准则。     

极小强连通本原有向图的本原指数集

本文的主要结果为:(1)当一个n阶极小强连通本原有向图至少含三个不同圈长时,有γ(D)≤[1/2(n~2-6n+14)](当n≥14时)。(2)e(n)≥[1/2(n~2-6n+16)],即从6到[1/2(n~2-6n+14)]的所有正整数都是某个n阶极小强连通本原有向图的本原指数。(3)给出了n阶极小强连通本原有向图的本原指数集NE_n的明确表达式。     

依赖团数的有向图极大弧连通的充分条件

互连网络通常以有向图为模型,有向图的弧连通度是网络可靠性的一个重要参数.设D是一个有向图,δ(D)是最小度,弧连通度为λ(D),则λ(D)≤δ(D).当λ(D)=δ(D)时,称有向图D是极大弧连通的.本文给出了依赖团数的有向图极大弧连通的一些充分条件.     

有向循环图强连通度的下界

为简便计,本文采用文[1]中的定义和符号,而未说明的概念或符号引自[3].本文仅讨论有限、简单有向图. 有向图D=(V,A)称为强连通的,如果对D的任两顶点u与v,在D中同时存在(u,v)—有向路和(v,u)—有向路,C(?)V称为D的点割集,如果D—C非强连通或是单点.D的所含点数最少的点割集称为最小点割集,其阶数定义为D的强连通度,记为k(D)或k. 循环有向图D(n,S)定义如下:     

有向线图的限制性连通度

设D=（y（D）,A（D））是一个强连通有向图．弧集S A（D）称为D的k-限制性弧割,如果D-S中至少有两个强连通分支的阶数大于等于后．最小k-限制性弧割的基数称为k-限制性弧连通度,记作Ak（D）．k-限制性点连通度Kk（D）可以类似地定义．有k-限制性弧割（k-限制性点割）的有向图称为λk-连通（kk-连通）有向图．本文研究有向图D的限制性弧连通度和其线图L（D）的限制性点连通度的关系,证明了对任意λk-连通有向图D,kk（L（D））≤λk（D）,当k=2,3时等式成立;若L（D）是Kk（k-1）连通的,则λk（D）≤Kk（k-1）（L（D））;特别地,若D是一个定向图且L（D）是Kk（k-1）／2．连通的,贝0Ak（D）≤Kk（k-1）,2（L（D））．     

α2-独立数为2的有向图中的迹,路和圈

设α₂(D)=max{|X|:X?V(D)且D[X]不含有向2-圈}是有向图D的α₂ (D)-独立数.在文献[Proc.London Math.Soc.,42 (1981) 231-251]中,Thomassen构造了满足κ(D)=α(D)的非哈密尔顿有向图D,以此证明Chvátal-Erd?s定理在有向图情形下不能得到自然推广.Bang-Jensen和Thomassé提出如下猜想:每一个满足弧强连通度大于等于其独立数的有向图一定包含生成闭迹.对于满足弧强连通度大于等于其α2(D)-独立数的有向图是否包含生成迹这一问题,目前仍未解决.如果对于D中的任意两个顶点x和y,D包含生成(x,y)-迹,或者生成(y,x)-迹,则称有向图D是弱迹连通的.如果对于D中的任意两个顶点x和y,D既包含生成(x,y)-迹又包含生成(y,x)-迹,则称D是强迹连通的.本文在确定两个强连通有向图类M和H的基础上,研究了在满足α₂(D)=2条件下,有向图D的相关结果,并得到以下结论:(ⅰ) D是哈密尔顿的当且仅当D?M.(ⅱ) D是弱迹连通的.(...     

γ-可图序列与γ-完全子图

一个r-图是一个无环的无向图,其中任何两个顶点之间至多被r条边连接.一个m+1个顶点的r-完全图,记为K_(m+1)^((r)),是一个m+1个顶点的r-图,其中任何两个顶点之间恰好被r条边连接.一个非增的非负整数序列π=(d_1,d_2,…,d_n)称为是r-可图的如果它是某个n个顶点的r-图的度序列.一个r-可图序列π称为是蕴含(强迫)K_(m+1)((r)),是一个m+1个顶点的r-图,其中任何两个顶点之间恰好被r条边连接.一个非增的非负整数序列π=(d_1,d_2,…,d_n)称为是r-可图的如果它是某个n个顶点的r-图的度序列.一个r-可图序列π称为是蕴含(强迫)K_(m+1)^((r))可图的如果π有一个实现包含K_(m+1)((r))可图的如果π有一个实现包含K_(m+1)^((r))作为子图(π的每一个实现包含K_(m+1)((r))作为子图(π的每一个实现包含K_(m+1)^((r))作为子图).设σ(K_(m+1)((r))作为子图).设σ(K_(m+1)^((r)),n)(τ(K_(m+1)((r)),n)(τ(K_(m+1)^((r)),n))表示最小的偶整数t,使得每一个r-可图序列π=(d_1,d_2,…,d_n)具有∑_(i=1)((r)),n))表示最小的偶整数t,使得每一个r-可图序列π=(d_1,d_2,…,d_n)具有∑_(i=1)ⁿ d_i≥t是蕴含(强迫)K_(m+1)n d_i≥t是蕴含(强迫)K_(m+1)^((r))-可图的.易见,σ(K_(m+1)((r))-可图的.易见,σ(K_(m+1)^((r)),n)是Erds等人的一个猜想从1-图到r-图的扩充且τ(K_(m+1)((r)),n)是Erds等人的一个猜想从1-图到r-图的扩充且τ(K_(m+1)^((r)),n)是经典Turan定理从1-图到r-图的扩充.本文给出了蕴含K_(m+1)((r)),n)是经典Turan定理从1-图到r-图的扩充.本文给出了蕴含K_(m+1)^((r))的r-可图序列的两个简单充分条件.此两个条件包含了Yin和Li在[Discrete Math.,2005,301:218-227]中的两个主要结果和当n≥max{m((r))的r-可图序列的两个简单充分条件.此两个条件包含了Yin和Li在[Discrete Math.,2005,301:218-227]中的两个主要结果和当n≥max{m²+3m+1-[(m2+3m+1-[(m²+m)/r],2m+1+[m/r]]}时,σ(K_(m+1)2+m)/r],2m+1+[m/r]]}时,σ(K_(m+1)^((r)),n)之值.此外,我们还确定了当n≥m+1时,τ(K_(m+1)((r)),n)之值.此外,我们还确定了当n≥m+1时,τ(K_(m+1)^((r)),n)之值.     

蕴含三类导出子图的可图序列

对非负整数序列π=（d1,d2……,dn),0≤di≤n-1,本分别给出了它蕴含导出子图为几乎处处完全图,完全图去掉一个Hamilton圈的边,完全k-部图可图（即蕴含aw^1,Aw^2和Ar,r2…,rk-可图）的判别准则。     

关于三圈连通标号图的计数公式

关于三圈连通标号图的计数公式张树生江西宁都固厚中学本文所指的图者是无向简单图。如果一个图恰好包含有ｍ个初级圈，那么就说这个图恰好包含有ｍ个单个的圈。Ｈａｒａｒｙ在［１］中提出了给定圈的个数的连通标号圈的计数问题。Ｒｅｎｙｉ在［２］中解决了单圈边通标号...     

可图序列偏序集的极小元

ｎ项非增非负整数序列是可图的,若是某个阶简单图的度序列．所有项和为２ｍ、迹为ｆ的ｎ项可图序列的集合Ｇ_ｎ,ｍ,ｆ在优超关系下是一个偏序集．本文刻划了偏序集Ｇ_ｎ,ｍ,ｆ的极小元,并确定各种可图序列偏序集中极小元的个数．     

路代数的有向图特征与Brown－McCoy根

本文解决路代数中若干遗留问题，给出本原路代数、（右）Ｇｏｌｄｉｅ路代数的有向图特征，证明广义路代数的Ｂｒｏｗｎ－ＭｃＣｏｙ根与它的Ｊａｃｏｂｓｏｎ根不必重合．     

关于K_（1，r）－free图的连通因子

本文证明了每个连通的Ｋ１，ｒ－ｆｒｅｅ图Ｇ，如果有［ｆ，ｇ］－因子Ｆ，则它就有包含Ｆ的［ｆ，ｇ＋ｒ－１］连通因子．