对一类有限图上连续自映射的熵的刻画

设G为除含一个圆周束外不含其它圈的有限图,证明了连续自映射f:G→G的熵为零当且仅当存在k≤[(Edg(G) End(G) 3C ir(G) 3)/2]个不同的奇数n1,n2,…,nk,使得Per(f)k∪i=1∪∞其中Edg(G)、End(G)、Cir(G)分别表示G的边数、端点数、圈数.     

关于非广义多边形路的2连通简单MCD图

令Sn是具有n个顶点没有两个等长圈的简单图的集合,若Sn中不存在图G′使│E（G′）│＞│E（G）│,则称图G是简单MCD图,若简单MCD图G是2连通的,则称G是2连通简单MCD图,若G中一条路P的两个内点u都有dG(v)=2,则称P为G的简单路,一个2连通可平面图G称为广义多边形路,如果用下述方法得到图G是路,对应于G的每个内部面f(G-是G的平图）有一个G＊的顶点f*,G*的两个顶点f*和g*,在G＊中相邻当且仅当G－中相应的两个内部面的边界交于一条G－的简单路,作者证明了下述结果,当且仅当n∈{10,11,14,15,16,21,22}时,存在n个顶点的非广义多边形路的2连通简单MCD图。     

分数(g,f,n′,m)-临界消去图的2个充分条件

设G是一个图,若去掉G中的任意n′个顶点的剩余子图仍是分数(g,f,m)-消去图,则称G是一个分数(g,f,n′,m)-临界消去图.从独立数和度条件2个角度出发,分别给出了图G是分数(g,f,n′,m)-临界消去图的2个充分条件.     

图Pn∨Km,n的均匀全色数

对于图G(V,E)的正常k-全染色f称为G(V,E)的k-均匀全染色,当且仅当任意2个色类中的元素总数至多相差1.eχt(G)=min{k|G有k-均匀全染色}称为G的均匀全色数.利用均匀边染色的相关结论,探讨了路Pn与完全二部图Km,n的联图Pn∨Km,n的均匀全色数.     

几类图的最优填充数

运用图的最优填充分解定理和局部最优填充定理,将一些特殊图类G1×G2,S(G),R(G)和双圈图分解为一些可求得最小填充数的图,得到如下结果:(1)F(Pm×Pn)≤(m-2)(n-2),其中m≥2,n≥2;(2)若G是有m条边的n阶2-连通图,则F(S(G))=m F(G);(3)设图G为双圈图,两个诱导圈的圈长分别为p和q,t为这两个圈公共部分的路上的顶点个数(不包括两个端点),则F(G)=p q-t-6.     

高度正则图的强边色数

设f是图G的一个正常边着色，若对G中任意不同的两点u,v，着在与u关联的边上的色集和着在与v关联的边上的色集不同，则称f为强边着色。满足此条件的最小色数称为G的强边色数，记为X^-′（G）。本文确定了对n阶（n-2）-度正则图G，X^-′（G）=n，当n≥6时，对其补图为Hamilton圈的n阶（n-3)-正则图G，X^-′（G）=n-1，还给出了对任意的一条边e，X^-′（G-e)≤X^-′（G） 1的一个充分条件和X^-′（G-e）=X^-′（G） 2的必要条件。     

Halin图的无圈边着色

设f是图G的一个正常边着色，若在f下G中没有2-色圈，则称f是图G的一个无圈边着色，其所用最小色数为G的无圈边色数。N．Alon猜想对所有简单图，无圈边色数不超过其最大度加2。本文证明了该猜想对Halin图成立，且当Δ≤4时，其色数不超过5；当Δ≥5时，其色数等于最大度。     

双圈图的N-G型的代数连通度的界

对任一个n阶单图G,用a(G)表示G的代数连通度,GC表示它的补图.针对双圈图,即边数等于顶点数加1的且只含有2个边不交的基本圈的简单连通图,证明了对任一n阶双圈图G,有1≤a(G)+a(GC),当且仅当G≌G1时等式成立.     

两个完全图的匹配和的L(p,q)-标号

设p,q为两个非负整数,一个图G的L(p,q)-标号是一个从G的顶点集V(G)到一个非负整数集的映射f,使得对于G中的任意两个顶点u,v,当d(u,v)=1时,|f(u)-f(v)|≥p;当d(u,v)=2时,|f(u)-f(v)|≥q;根据p,q之间的关系,给出两个顶点数都是n的完全图的匹配和的L(p,q)-标号数的上界.而当q≤p≤2q时,确定了两个顶点数都是n的完全图的匹配和的L(p,q)-标号数的准确值.     

非连通图(P_1∨P_m)∪C_(4n)∪P_2的优美性

讨论非连通图(P1∨Pm)∪C4n∪P2的优美性.证明如下结论:设m、n为任意正整数,当m≥2,1≤n≤2m-2时,非连通图(P1∨Pm)∪C4n∪P2是优美图,其中Pn是n个顶点的路,G1∨G2是图G1与G2的联图,C4n是4n个顶点的圈.     

一类3-正则图的关联邻点可区别全染色

对简单图G(V,E),f是从V(G)∪E(G)到{1,2,...,k}的映射,k是自然数,若f满足(1)uv∈E(G),u≠v,f(u)≠f(v);(2)uv,uw∈E(G),v≠w,f(uv)≠f(uw);(3)uv∈E(G),C(u)≠C(v);其中C(u)={f(u)}∪{f(uv)|uv∈E(G)};则称f是G的一个关联邻点可区别全染色.给出了一类3-正则重圈图Re(n,m)(m≥2,n≥3且n≡0(mod2))的关联邻点可区别全色数.     

泛圈图的一个充分条件

本文证明了:如果G是n(≥9)阶2连通无爪图,且G的每个导出子图Z_1,满足当u,v∈V(G)d_(z_1)(u,v)=2时有|N(u)UN(v)|≥n-3,则G是泛圈图或圈.其中Z_1≌(K_2UK_1)VK_1.     

关于一类(g,f)-2-消去图的研究

一个图G称为一个(g,f) 2 消去图,如果G的任何两条边不属于它的一个(g,f) 因子,本文得到了如下结论:(ⅰ)当g≤f时一个二部图是(g,f) 2 消去图的一个充分必要条件;(ⅱ)一个二部图是f 2 消去图的简单判别准则.     

二分图中度条件与[a,b]-覆盖图

设G是一个图,用V(G)和E(G)表示它的顶点集和边集,并设g和f是定义在V(G)上的两个整数值函数且g相似文献   

关于一类(g,f)-2-覆盖图的研究

一个图G称为(g,f)-2-覆盖图,如果G的任何两条边都属于它的一个(g,f)-因子,得到了如下结论:(1)当g≤f时,一个二部图是(g,f)-2-覆盖图的一个充分必要条件;(2)当f(X)=f(Y)时,一个二部图是f-2-覆盖图的一个充分必要条件及其简单判别准则.     

关于冠图的关联着色

设 G =( V,E)是一个图 ,称 I( G) ={ ( v,e) |v∈ V,e∈ E,v与 e相关联 }是 G的关联集 .I( G)的两元素 ( v,e)和 ( w,f )是相邻的当且仅当下列三条之一成立 :( 1) v=w;( 2 ) e=f ;( 3) vw =e或 f .图 G的关联着色是从 E( G)到一颜色集 C的映射 ,使得 E( G)中任何两相邻元素有不同的像 ,其中 C中所含元素的最小个数称为 G的关联色数 ,记为 inc( G) .这一概念是 Brualdi等在 1993年提出的 ,并提出了如下猜想 :每个图都能用Δ ( G) +2种颜色进行关联着色 .本文证明了对于树图、轮图、扇图、圈和完全二部图的冠图猜想成立 .     

△(G)=6时的Halin图的可区别数

结合n阶圈Cn可区别数的证明,得证了△(G)=6时n阶以上Halin图G的可区别数分别2,△(G)表示图G的最大顶点度.     

一类广义Petersen图的L(2,1)-标号

图G的L(2,1)-标号是从图G的顶点集到非负整数集的一个映射f∶V(G)→{0,1,2,…},它满足对任意两个顶点x,y,当d(x,y)=1时,|f(x)-f(y)|≥2;当d(x,y)≥2时,|f(x)-f(y)≥1.研究了n≡0(mod3)的广义Petersen图G=P(n,t)的L(2,1)-标号数λ2,1(G),得到当t=0(mod3),5≤λ2,1(G)≤8,否则λ2,1(G)=5     

泛圈图的一个充分条件

设G是一个n阶2—连通图且δ(G)≥4,本文证明了:若对于G中任意距离为2的两点u和ν均有|N(u)∪N(ν)|≥n-4.则G是泛圈图或n=8且G≌K_(4.4)。     

图的强直积的2-距离染色(英文)

设G,H是阶至少为2的简单图。图G与H的强直积是指这样一个图G□×H,其顶点集合为V(G)×V(H),并且(x1,x2)(y1,y2)∈E(G□×H)当且仅当[x1y1∈E(G)且x2y2∈E(H)]或者[x1=y1且x2y2∈E(H)]或者[x2=y2且x1y1∈E(G)]。一个图G的使用了k种颜色的2-距离染色是指一个从V(G)到{1,2,…,k}的映射f,使得任意两个不同的距离最多是2的顶点染不同的颜色。对图G进行2-距离染色所需的最少的颜色数称为图G的2-距离色数,记为χ2(G)。文中将获得两个图的强直积的2-距离色数的可达到的上界和下界:Δ(G□×H)+1≤χ2(G□×H)≤χ2(G).χ2(H)。对一些特殊图,例如Pm□×Kn,Pm□×Wn,Pm□×Sn,Pm□×Fn,Pm□×Cn(n≡0(mod3)或者n=5),给出了它们的2-距离色数。