拟正则完全二部图的局部最可靠性

用P(G，ρ)表示顶点完全可靠，而边则以概率ρ∈(0，1)相互独立地出现故障的图G的全终端不可靠度，即G因边故障而变得不连通的概率．本文证明了边故障率ρ充分小时，拟正则完全二部图在具有相同点数和相同边数的图类中是惟一具有最小全终端不可靠度的图．     

K_(n,n)的局部最优可靠性

假设n点m边的简单无向图G=(V,E)的每个顶点完全可靠,各边相互独立地以同一概率q(0q1)发生故障,则用G不连通的概率P(G,q)作为衡量网不可靠程度的指标.如果对于充分接近q0的所有q都有P(G,q)P(H,q),则称在边故障概率q～q0时,网络G比H可靠.证明了当q～0时,Kn,n(n4)是2n点n2边图中局部最优可靠的.     

关于图的若干介值问题

对连通图G,以C_i(G),■(G)分别表G的有i条边的连通支撑子图之集与连通子图之集,以C~i(G),(?)(G)分别表G的顶点数为i的子树集与连通子图之集.本文讨论了这四类子图簇对若干基本参数及端点数的介值性,从而对已有的一些结果作了若干有意义的拓广.     

某些对角方程在有限域上的解数

主要运用Gauss和以及Jacobi和的相关性质给出两类对角方程在有限域上的解数公式,分别是形如s∑(i=1) a_ix_i~(m_i)=c的对角方程,其中a_i,c∈F_q~2~*,(m_i,m_j)=1,m_i|(q+1),m_i为奇数或(q+1)/(m_i)为偶数,i=1,2,…,s,以及形如s∑(i=1) x_i~m=c的对角方程,其中c∈F_q~*,m|(q+1),m为奇数或(q+1)/m为偶数.     

图 P2×Cn的均匀邻强边色数

对图G(V,E),一正常边染色f若满足(1)对(V)uv∈E(G),f[u]≠f[v],其中f[u]={f(uv)|uv∈E};(2)对任意i≠j,有||E|-|Ej||≤1,其中Ei={e| e∈E(G)且f(e)=i}.则称f为G(V,E)的一k-均匀邻强边染色,简称k-EASC,并且称Xcas(G)=min{k|存在G(V,E)的一k-EASC为G(V,E)的均匀邻强边色数.本文得到了图P2×Cn的均匀邻强边色数.     

证明图ρ_n~G(i)∪G等的伴随分解及色等价性

设P_m和C_m分别表示具有m个顶点的路和圈,G是任意的r阶连通图,设m是偶数,把路P_(m-1)的标号为偶数的2~(-1)m个顶点分别与2~(-1)mG每个分支的第i个顶点V_i重迭后的图记为ρ_((m-1)+2~(-1)mr)~G(i),令n=(2m+1)+(m+1)r,把图kρ_n~G(i)的每个分支的一个d(v_i)+1度顶点分别与S_(k+1)的k个1度点重迭后所得到的图记为Y_(kn+1)~(PG),运用图的伴随多项式的性质,首先给出了一类图簇ρ_n~G(i)和Y_(kn+1)~(PG)的伴随多项式.在讨论上述图的伴随多项式的基础上,证明了图ρ_n~G(i)∪G、Y_(kn+1)~(PG)∪(k-1)K_1和Y_(kn+1)~(PG)∪(k-1)K_1∪(k-1)G的伴随多项式的因式分解定理,进而证明了这些图类的补图的色等价性.     

关于哈密顿线图的一个注记

一、 引言令 G 是顶点集合为 V(G)且边集合为 E(G)的简单图.图 G 的线图 L(G)是顶点集合为 E(G)的图,L(G)的两个顶点,e_1和 e_2是相邻接的当且仅当 e_1和 e_2在 G中有一个公共顶点.图 G 的一条通道是点与边的一个交替序列 v_0,e_1,v_1,…,v_(n-1),e_n,v_n 其中 e_i(i=     

论图的最大特征根

1.前言 对于一个图G,以下指的都是无环、无重边的有限无向图,我们用A(G)记G的联系矩阵(adjacency matrix)。由于A(G)是非负方阵,故必有最大特征根,记为ρ(G),简称为G的大根。本文对图G和它的大根ρ(G)间的相互联系就下述两个方面的问题进行探讨: (Ⅰ)大根ρ(G)有什么图论意义? (Ⅱ)当G进行某种变形时,ρ(G)必随之相应变化,此中有无内在规律?     

图的孤立韧度与分数k-覆盖图

设G是一个图,若对于图G的任一条边e,都存在一个分数k-因子h,使得h(e)=1,则称图G是分数k-覆盖图.图G的孤立韧度I(a)定义为:若G是完全图,则I(C)= ∞;否则,I(G)=min{|S|/i(G-S):SCV(G),i(G-S)≥2},其中i(G-S)表示G-S中的孤立点数目.本文首次提出并研究了一个图是分数k-覆盖图与它的孤立韧度之间的关系,证明了当I(G)>k,并且δ(G)>k 1时,G是分数k-覆盖图.我们还证明了,这个结果是最好可能的.     

与单形重心有关的几个几何不等式

设A_0A_1…A_n为n维欧氏空间E~n中的一个单形S,其重心为G,A_iG交A_i的对面于G_i(G_i为(n-1)维单形A_0A_1…A_(i-1)A_(i 1)…A_n的重心),交S的外接超球面F于A_i~1(i=0,1,…,n)。记S的棱长分别为α_(ij)=(i,j=0,1,…,n,i≠j),其中线长为m_i=(i=0,1,…,n),我们将证明如下的     

图的非负广义邻接矩阵的谱半径的一些界（英文）

顶点数为n,边数为m的简单图G的非负广义邻接矩阵定义为U(G)=γAA(G)+γ_II(G)+γ_JJ(G)+γ_DD(G),其中γ_A,γ_I,γ_J,γ_D是一些非负实数,A(G)是图G的邻接矩阵,D(G)=diag(d₁,d₂,…,d_n),I(G)是单位矩阵,J(G)是全1矩阵.本文得到了谱半径ρ_U(G)的一些界,并刻画了达到这些界时的极图.此外还得到了ρ_Aα(G)的新界以及ρ_A(G),ρ_L(G)和ρ_Q(G)的已知界.     

粘合运算对图的控制参数的影响

简单图G的粘合运算G_(uv)指的是重合G的两个顶点{u,v}并且去掉重边和环所得到简单图的运算．本文考虑了粘合运算对图的4个控制参数γ(G),Γ(G),β(G),i(G)的影响．刻画了图G_(uv)与图G的控制参数γ(G),Γ(G),γ(G),i(G)之间的关系．及给出γ(G_(uv))=γ(G)-1和β(G_(uv)=β(G)-1的充要条件．     

关于极大外平面图的度偏差的极值

设G是一个由n个顶点,m条边构成的简单连通图.如果图G所有顶点的度相同,则我们称图G是正则图,反之,称图G是不规则图.对于一个不规则图G,由其不变量定义的度偏差为s(G)=∑_(i=1)^(n)|d_(i)-2m/n|,其中d_(i)表示G的第i个顶点的度.本文给出极大外平面图的度偏差的极大值和极小值,并刻画其对应的极值图.     

一个最小可行图的判定条件

设有n个集合X_1,…,X_n,一个以X=U_(i=1)~nX_i为顶点集的图G称为是一个关于(X_1,…,X_n)的可行图,如果对每一个X_i(i=1,…,n),导出子图G_i=G[Xi]是连通的。关于集合序列(X_1,…,X_n),含最少边数的可行图称为是最小可行图。本文证明,关于(X_1,X_2,X_3)的可行图G=G_1∪G_2∪G_3是最小可行图的充分必要条件是:当X_i∩X_j∩X_k≠φ(i,j,k)=1,2,3)时,G_i∩G_j∩G_k是树。它发展了由D.-Z.Du(堵丁柱)在1986年得到的一个结果。     

T-染色和G_n~d图的T-边柞(Edge Span)

给定一个包含0的有限正整数集T,一个简单图G的一个T-染色是定义在G的顶点集V(G)上的一个非负函数f,满足对任意的uv∈E(G)有|f(u)-f(v)| T.一个T-染色f的边柞(edgespan)定义为最大的|f(x)-f(y)|,xy∈E(G),一个图G的边柞(edgespan)是G的所有T-染色中最小的边柞(edgespan).这篇文章研究了当T={0,1,2,…,k-1}时,Gdn图的T-边柞(edgespan),找到了当n≡1(modd)时Gdn图的T-边柞(edgespan)的确切值,和其他情况下的上下界.     

最大度与最小度相差不超过2的图的平衡judicious划分

图G的顶点集V(G)的一个二部划分V_1和V_2叫做平衡二部划分,如果||V_1|-|V_2||≤1成立.Bollobas和Scott猜想:每一个有m条边且最小度不小于2的图,都存在一个平衡二部划分V_1,V_2,使得max{e(V_1),e(V_2)}≤m/3,此处e(V_i)表示两顶点都在V_i(i=1,2)中的边的条数.他们证明了这个猜想对正则图(即△(G)=δ(G))成立.颜娟和许宝刚证明了每个(k,k-1)-双正则图(即△(G)-δ(G)≤1)存在一个平衡二部划分V_1,V_2,使得每一顶点集的导出子图包含大约m/4条边.这里把该结论推广到最大度和最小度相差不超过2的图G.     

图的半强积的邻点可区别染色

两个简单图G与H的半强积G·H是具有顶点集V(G)×V(H)的简单图,其中两个顶点(u,v)与(u',v')相邻当且仅当u=u'且vv'∈E(H),或uu'∈E(G)且vv'∈E(H).图的邻点可区别边(全)染色是指相邻点具有不同色集的正常边(全)染色.统称图的邻点可区别边染色与邻点可区别全染色为图的邻点可区别染色.图G的邻点可区别染色所需的最少的颜色数称为邻点可区别染色数,并记为X_a~((r))(G),其中r=1,2,且X_a~((1))(G)与X_a~((2))(G)分别表示G的邻点可区别的边色数与全色数.给出了两个简单图的半强积的邻点可区别染色数的一个上界,并证明了该上界是可达的.然后,讨论了两个树的不同半强积具有相同邻点可区别染色数的充分必要条件.另外,确定了一类图与完全图的半强积的邻点可区别染色数的精确值.     

图的{P_4}—分解

一个图G的路分解是指一路集合使得G的每条边恰好出现在其中一条路上.记Pl长度为l-1的路,如果G能够分解成若干个Pl,则称G存在{Pl}—分解.关于图的给定长路分解问题主要结果有:(i)连通图G存在{P3}—分解当且仅当G有偶数条边(见[1]);(ii)连通图G存在{P3,P4}—分解当且仅当G不是C3和奇树,这里C3的长度为3的圈而奇树是所有顶点皆度数为奇数的树(见[3]).本文讨论了3正则图的{P4}—分解情况,并构造证明了边数为3k(k热∈Z且k≥2)的完全图Kn和完全二部图Kr,s存在{P4}—分解.     

几族3-优图

一个图 G中含有的三个结点的导出连通子图的个数 S3( G)在网络可靠性中起着重要作用 .在同点数同边数图类中具有最大 S3( G)的图称为 3-优图 ,它所代表的网络是点故障概率接近 1时的最可靠网络 .本文在已有的结果上进一步证明补图为 a K3∪ b K2 ∪ K1和 a K3-x的图分别是各自图类中唯一的 3-优图 ;补图为 a K3∪ ( b-1 ) K2 ∪ 2 K1和 ( a-1 ) K3∪ b K2 ∪ P3的图是该图类中仅有的两个 3-优图 .     

边覆盖染色问题的有效算法

设G=(V,E)是一个重图.若边子集F的导出子图是G的一个生成子图,则称F为G的一个边覆盖.G的边覆盖色数ξ(G)是使得G可划分的最大不交边覆盖数.用δ(G)表示G的最小阶,令ρ(G)=min{2|?(U)|/(|U|+1):U?V(G),|U|≥3为奇数},其中?(U)表示至少有一个端点在U中的边集合.显然,ξ(G)≤min{δ(G),「ρ(G)」}.本文证明了,对系列平行重图和近似二部重图,此处等号成立,并且通过证明得到计算这两类重图的边覆盖色数的多项式时间算法.