最小度和[a,b」——覆盖图

设 a≤ b是整数,G=(V(G),E(G))是一个图G的一个支撑子图F称为G的一个[a,b]—因子,若对任意的v∈V(G),有a≤d_F,(v)≤b.图G称为是[a,b]—覆盖图,若对G的每一条边,存在G的一个[a,b]）—因子包含它,本文给出了一个图是[a,b]—覆盖图的关于最小度的充分条件,证明了下列结果;设1≤an (a b)-2(bn-1)~(1/2)则G是一个[a,b]—覆盖图.     

分数ID-[a,b]-因子临界图的最小度与独立数条件(英文)

对图G的每个独立集I,若G-I有分数[a,b]-因子,则G是分数ID-[a,b]-因子临界图.本文证明了若α(G)≤(4b(δ(G)-b+1))/((a+1)2+4b),则G是分数ID-[a,b]-因子临界图.     

■图的色唯一性

设G是简单图,用P(G,λ)表示图G的色多项式,若P(G,λ)=P(H,λ),则称G与H是色等价的,简单的表示为H~G.记[G]={H|H~G}.若[G]={G},称G是色唯一的.本文给出了(∪iCi)∪(∪jDj))图色唯一的相对于文献[1]、[2]中的结论更为一般的结论.     

(∪iCi)∪(∪jDj)图的色唯一性

设G是简单图,用P(G,λ)表示图G的色多项式,若P(G,λ)=P(H,λ),则称G与与H是色等价的,简单的表示为H～G.记[G]={H|H～G}.若[G]={G},称G是色唯一的.本文给出了(∪iCi)∪(∪jDj))-图色唯一的相对于文献[1]、[2]中的结论更为一般的结论.     

若干图的广义字典积的点可区别边染色

在图G与不相交图序列hn=(Hi)i∈{0,1,…,n-1}的广义字典积G[hn]中,若Hi≌H,i=0,1,…,n-1,则将G[hn]记为G[H],其中G[H]是G与H的字典积。图G的点可区别边染色所需最少的颜色数称为G的点可区别边色数,记为χ'vd(G)。对任一满足χ'vd(G)=Δ(G)的图G,给出了参数χ'vd(G[hn])的两个上界,并证明这些上界是可达到的,其中hn=(Hi)i∈{0,1,…,n-1}中的每一个Hi均为m阶简单图。另外证明了:如果χ'vd(G)=Δ(G),χ'vd(H)=Δ(H)且Δ(G[H])=Δ(H[G]),则χ'vd(G[H])=χ'vd(H[G]),其中G与H分别为n阶与m阶的简单图。     

具有完美匹配图的一个新特征

0 引言 [1]中指出,一个图G什么时候有一个完美匹配?这个比较困难的问题在1947年为加拿大著名图论学者托特(Tutte)所解决。托特所给出的具有完美匹配的图的特征是用G的奇支来描述的。G的一个奇支,是指图G的一个支中有奇数个点。G中奇支的数目记作oc(G)。于是,一个图G有一个完美匹配当且仅当对任何S(G),有oc(G-S)≤|S|。本文利用文[2]提出的“等秩变换”,     

图的字典积的整数流

得到对连通图G1和阶数大于3的图G2,他们的字典积G1[G2]有非零4-流.特别当G2是二部图时,G1[G2]有非零3-流.通过一个完全不同的方法,也得到了如果G1有非零3-流且具有完美匹配或G2有非零3-流,那么G1[G2]有非零3-流.     

高斯整数环的商环的5次幂映射图

令Z[i]为高斯整数环,Z_n[i]为模n高斯整数环.定义Z_n[i]上的5次幂映射图G(n),该映射图的顶点为Z_n[i]中的所有元素,并且,对于图中的2个顶点α和β,如果β=α~5,则从α到β有一条有向边.通过解高次同余方程以及利用高斯整数环的商环的单位群结构,对映射图G(n)的结构进行了研究,获得G(n)中不动点的个数,顶点0、1的入度计算公式,以及G(n)为半正则图的充要条件.     

若干倍图的邻点可区别的I-均匀全染色

对图G的一个邻点可区别的I-全染色f,若f还满足任意两种颜色所染元素(点和边)个数最大相差为1,则称f为图G的一个邻点可区别的I-均匀全染色.对图G进行邻点可区别的I-均匀全染色所需最少的颜色数称为图G的邻点可区别I-均匀全色数.研究了图D(C_n),D(S_n),D(F_n),D(W_n)的邻点可区别I-均匀全染色,通过函数构造法,得到了其的邻点可区别I-均匀全色数,并验证了其满足猜想:χ■(G)≤Δ(G)+2.     

椭园型方程广义解的Hlder连续性

本文对文[1]作如下推广:文[1]关于α(x)和,f(x)是在α(x),f(x)∈L_p(G),p=n/(1-λ)条件下([1]中误为p=n/(2-λ))得到一系列结果,本文在α(x),f(x)∈L_p(G),     

关于Betti亏数的一个结果的改进

一个连通图G的最大亏格主要由其参数Betti亏数ξ(G)确定，本文推广了黄元秋，赵霆雷在文[4]中关于ξ(G)的结果，从而得到了关于ξ(G)的一个新结果．     

图的顶点划分与图的上可嵌入性

图G的顶点W-划分是指G的一个顶点划分{V1,V2,…,Vs),其中G[Vi]有生成子图轮W[V1](1≤i≤s).结合图的顶点W-划分以及顶点度条件,得到了一类新的上可嵌入图类,推广了已有相关结果.     

图与补图断裂度的关系

在这篇文章中,作者解决了图与补图断裂度关系的问题.主要结果:1、若n(≥4)阶图G与(?)都连通,则(1)-(n-5)≤B(G)_B(G)≤n-2:(2)对[-(n-5),n-2]中任一整数r,都存在G,使B(G)+B(?)=r.2、若n(≥5)阶图H与(?)都是Hamilton图,则(1)-(n-5)≤B(H)+B(?)≤0;(2)对[-(n-5),0]中任一整数r,都存在互补的Hamilton图H和(?)使B(H)+B(?)=r.     

关于标定不相交图并图的树的计数

本文就不相交的标定图的并图G =(V ,E) ,讨论当顶点选自V ,而边不属于E时所能构成树的棵数 ,其中得到的一些结果为文[1 ] [2 ] 等的一些结论的推广 .     

对高踪《关于标定图重构的一条定理》一文的意见

我院学报(自然科学版)1986年第2期发表了一篇文章[1].[1]言称证明了Ulam猜想成立,而且是“标定图G可由其任意三个不同的标定子图重构”.[1]的作者在证明中使用了De Morgan公式,这实际上等于事先已经不自觉地承认了母图G是唯一确定的.如果仅仅从三个子图出发去考虑.那么它们重构什么样的母图,情况是非常复杂的.简单地套用De Morgan公式,难免会得出错误的结论.现针对文[1]举一反例如下:     

2-连通图中X-最长圈下界估计

给一个图G,XV(G),G[X]为G的X生成子图,r为正整数。定义α(X)=max｛｜S｜｝S是G[X]的顶点独立集｝,αk(X)=min｛∑ki=1d(vi)｜｛v1,v2,…,vk｝是G[X]的顶点独立集},NCk(X)=min｛｜Uki=1N(vi)｜｛v1,…,vk是G[x]的独点独立集}(k≥2)．我们得到结论;对—任意的n阶2-连通图G(n≥3),xG,且α3(X)≥n+r≥n+2,则存在一个包含X的顶点数为min｛｜X｜,[X]+NC,+2+e(n+r)(X)-α(X)}的圈,ε(i)=3〔1-3i〕-1-3i.该结论推广了H.J.Broersma在文献[1]中的结果．     

图的邻域并和连通的[k,k+1]-因子

设G是阶为n的图.F是G的支撑子图且对所有的x∈V(G)都有k≤dF(x)≤k+1,则称F为G的[k,k+1]-因子.一个[k,k+1]-因子如果连通,则称为连通的[k,k+1]-因子.一个[k,k+1]-因子若包含一个哈密顿圈,则称为哈密顿[k,k+1]-因子.给出了图有哈密顿[k,k+1]-因子或连通的[k,k+1]-因子关于邻域并的若干新的充分条件.     

若干n重积图的点可区别边色数

通过研究若干n重积图的边色数及点可区别边色数,就可证明■(Gi)=△(Gi),i=1,2,L,n,则∑=′×××=■△(G_i)其中G1×G2×L×Gn为G1,G2,L,Gn的n重积图.     

完全三部图K(2,4,6)的色唯一性

设G是简单图,用P（G,λ）表示图G的色多项式．若对任意图H使P（H,λ）＝P（G,λ）,都有H与G同构,则称G是色唯一图．作者证明了：完全三部囹K（2,4,6）是色唯一图．从而解决了文[1]中的一个遗留问题．     

自同构群作用下具有两个轨道的连通图的连通性(英文)

若连通图G在自同构群作用下具有两个轨道V1和V2且满足|V1|=|V2|;G[V1]是k-正则图;G[V2]是r-正则图且G[V1V2]是l-正则图,则K(G)≥min{k,r}+1.构造的例子表明上述结果是最好可能的.