P_n~k的均匀全染色

设G(V,E)是一个简单图,f是G的一个k-正常全染色,若f满足||Vi∪Ei|-|Vj∪Ej||≤1(i≠j),其中Vi∪Ei={v|f(v)=i}∪{e|f(e)=i},则称f为G的k-均匀全染色,简记为k-ETC.并称eχT(G)=min{k|G存在k-均匀全染色}为G的均匀全染色数.本文将通过很好的全染色方法得到eχT(Pkn)=5(n≥2k+1),并证明了对Pkn,[5]中猜想是正确的.     

Pkn的均匀全染色

设G(V,E)是一个简单图,f是G的一个k-正常全染色,若f满足||Vi∪Ei|-|Vj∪Ej||≤1(i≠j),其中Vi∪Ei={v|f(v)=i}∪{e|f(e)=i},则称f为G的k-均匀全染色,简记为k-ETC.并称χeT(G)=min{k|G存在k-均匀全染色}为G的均匀全染色数.本文将通过很好的全染色方法得到χeT(Pkn)=5(n≥2k 1),并证明了对Pkn,[5]中猜想是正确的.     

图和补图的全色数

本文用不同于[3]的方法,研究了图及其补图全色数间的关系,得到了其中 p=|V(G)|,G°为 G 的补图。该结果包含了[3]的结果,且当 P 为偶数时更强。§1 引言对于简单图 G=(V,E),使 V∪E 的任何两个相邻或相关联的元素均有不同颜色所需要使用的最少颜色的数目,被称为 G 的全色数,记为 x_T(G)。使用一组颜色着染一个图G 的顶点和边,使得 V∪E 中任意两个相邻或相关联元素均有不同颜色,则称这个着色为     

完全图全符号控制数的较小上界和下确界

设图G=G(V,E),令函数f∶V∪E→{-1,1},f的权w(f)=∑x∈V∪Ef[x],对V∪E中任一元素,定义f[x]=∑y∈NT[x]f(y),这里NT[x]表示V∪E中x及其关联边、邻点的集合.图G的全符号控制函数为f∶V∪E→{-1,1},满足对所有的x∈V∪E有f[x]1,图G的全符号控制数γT(G)就是图G上全符号控制数的最小权,称其f为图G的γT-函数.本文得到了完全图全符号控制数的一个较小上界和下确界.     

星和轮的Mycielski图的[r,s,t]色数

给定非负整数r,s和t,若图G(V,E)有一个映射σ:V∪E→{0,1,…,k-1},k∈N,满足对V中相邻的点v_i,v_j有|σ(v_i)-σ(v_j)|≥r;对E中相邻的边e_i,e_j有|σ(e_i)-σ(e_j)|≥s;对V∪E中相关联的点v_i和边e_j有|σ(v_i)-σ(e_j)|≥t,则称σ为G的一个[r,s,t]-着色.使得图G存在使用了k种颜色的[r,s,t]-着色的最小整数k称为G的[r,s,t]-色数.研究星和轮的Mycielski图的[r,s,t]-着色,并给出其在一定条件下的[r,s,t]-色数.     

可圈的一个充分条件

本文我们证明如下结果:设G=(V,E)是一个n(n≥3)阶k-连通(k≥2)图,记X1,X2,…,Xk为V的子集,X=X1∪X2∪…∪Xk.若对每个I,I=1,2,…,k,满足:对任意的u,v∈Xi,有d(u) d(v)≥n或|N(u)∪N(v)|≥n-δ或|N(u)∩N(v)|≥α,这里δ是G的最小度,α是G的独立数,则G是X-可圈的.     

联图Fn∨Pm的邻点可区别全染色

设G(V,E)是阶数至少为2的简单连通图,k是正整数,V∪E到{1,2,3,…k}的映射f满足:对任意uv,uw∈E(G),u≠w,有f(uv)≠f(vw);对任意uv∈E(G),有f(u)≠f(v), f(u)≠f(uv),f(v)≠f(uv);那么称f为G的k-正常全染色,若f还满足对任意uv∈E(G),有G(u)≠C(v),其中C(u)={f(u)}∪{f(uv)|uv∈E(G),v∈V(G)}那么称f为G的k-邻点可区别的全染色(简记为k-AVDTC),称min{k|G有k-邻点可区别的全染色}为G的邻点可区别的全色数,记作Xat(G)．本文得到了联图Fn∨Pm的全色数．     

图的极大Tutte集的几个有效算法

图G=(V,E)的Tutte集定义为X■V(G)满足ω_o(G-X)一|X|=def(G).若不存在Tutte集Y■X,则称X为图G的极大Tutte集.通过找极大extreme集和D-图的极大独立集给出一般图G的找极大Tutte集的两个有效算法,并给出结论:X■V(G)是二部图G的极大Tutte集当且仅当X为二部图G的最小覆盖,从而得到找二部图G的极大Tutte集的一个有效算法.     

几类有趣图的奇优美性和奇强协调性

对于简单图G=〈V,E〉,如果存在一个映射f:V(G)→{0,1,2,…,2|E|-1}满足:1)对任意的u,v∈V,若u≠v,则f(u)≠f(v);2)max{f(v)|v∈V}=2|E|-1;3)对任意的e_1,e_2∈E,若e_1≠e_2,则g(e_1)≠g(e_2),此处g(e)=|f(u)+f(v)|,e=uv;4)|g(e)|e∈E}={1,3,5,…,2|E|-1},则称G为奇优美图,f称为G的奇优美标号.设G=〈V,E〉是一个无向简单图.如果存在一个映射f:V(G)→{0,1,2,…,2|E|-1},满足:1)f是单射;2)■uv∈E(G),令f(uv)=f(u)+f(v),有{f(uv)|uv∈E(G)}={1,3,5,…,2|E|-1},则称G是奇强协调图,f称为G的.奇强协调标号或奇强协调值.给出了链图、升降梯等几类有趣图的奇优美标号和奇强协调标号.     

若干Mycielski图的邻点可区别E-全染色

设G(V,E)是简单连通图,k是正整数,若V∪到{1,2,3,…,k}的映射f满足对任意uv∈E(G),有f(U)≠f(v),f(u)≠f(uv)f(v)≠f(uv),且C(u)≠C(v),其中C(u):{f(u)}∪{f(uv)|uv∈E(G)}.那么称f为G的k-邻点可区别的E-全染色(简记为k-AVDETC),并称X_(at)~e(G)=min{k|G有k-邻点可区别的E-全染色}为G的邻点可区别的E-全色数.本文讨论了路、圈、扇、星、轮及完全图的Mycielski图的邻点可区别E-全染色,得到了该类图的邻点可区别的E-全色数.     

△=3的图的邻和可区别全可选性（英文）

设图G=(V,E),φ:V∪E→{1,2,…,k}为图G的一个正常全染色.令f(v)表示点v及所有与其关联的边的颜色的加和.若对任意uv∈E(G),有f(u)≠f(v),则称φ是图G的邻和可区别全染色.Pilsniak和Wozniak最早研究了邻和可区别全染色,并猜想对于任意图G,若k≥△(G)+3,则其存在邻和可区别全染色.图G的最大平均度,记为mad(G),是G的所有非空子图的平均度的最大值.本文运用组合零点定理与权转移方法证明了:若图G满足△(G)=3且mad(G)(44)/(15),则ch_Σ″(G)≤6(其中ch_Σ″(G)为图G的邻和可区别全可选性).     

一类正则循环图的Cartesian积图的D(β)-点可区别Ⅵ-全染色及Ⅰ-全染色

设G是简单图,若图G的全染色f满足:1)(V)uv,vw∈E(G),有f(uv)≠f(vw);2)(V)uv∈E(G),u≠v,有f(u)≠f(v);3)(V)u,v∈V(G),0＜d(u,v)≤β,有S(u)≠S(v),这里色集合S(u)={f(u)}∪{f(uv) |uv∈E(G)}.则称f是图G的一个D(β)-点可区别Ⅰ-全染色.若f只满足条件1)和3),则称f是图G的一个D(β)-点可区别Ⅵ-全染色.研究了当β=1,2时一类正则循环图与圈的Cartesian积图的D(β)-点可区别Ⅵ-全色数和D(β)-点可区别Ⅰ-全色数,并讨论了正则图的D(β)-点可区别Ⅵ-全色数和D(β)-点可区别Ⅰ-全色数的上界.     

图 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的均匀邻强边色数.     

交叉立方体网络的反馈数

对于简单图G=(V,E),顶点子集F■V,如果由V\F导出的子图G′= (V\F,E′)是不含圈的,则称F是图G的一个反馈点集.点数最少的反馈点集称图的最小反馈点集,最小的点数称为反馈数.文章给出了交叉立方体网络的一个等价定义,用递归的方法构造出交叉立方体网络的诱导树,证明了诱导树的阶数Fibonacci数,进而得到叉立方体网络反馈数的上下界.     

图有[a,b]因子的邻域条件

不含有图K1，R的图称为K1,r-free图，设G是一个具有顶点集V（G）的图，设n(≥3),a和b是整数，使得b≥a≥1，若b是奇数，设b≥n-1。我们证明了每个连通的K1,r-free图G在b|V(G)|为偶数，它的最小度至少是a n-1,|V(G）≥ （2(a b)-1)(a b-1)/b，以及|NG(x）∪NG（y)|≥a|V(G)|a b对V的任意两个不邻接的点x和y都成立时，G有一个[a,b]因子。     

图与补图全独立数间的关系

对图G(V,E),V∪E中既不相邻、又不相关联的最大元素个数,称为G的全独立数,并简记为α_T(G)。本文研究了图和补图全独立数之间的关系,得到α_T(G) α_T(G~C)≤「3y 1/2」。其中y=|V(G)|,G~C是G的补图,「x」为不大于x的最大整数,且界可达。     

Pkn(k≡2(mod 3))的邻点可区别的强全染色

对简单图G(V,E),V(Gk)=V(G),E(Gk)＝E(G)U{uv|d(u,v)=k},称Gk为G的k次方图,其中d(u,v)表示u,v在G中的距离.设f为用k色时G的正常全染色法,对 uv∈E(G),满足C(u)≠C(v),其中C(u)＝{f(u)}U{f(v)|uv∈E(G)}U{f(uv)|uv∈E(G)},则称f为G的k邻点可区别的强全染色法,简记作k-ASVDTC,且称Xast(G)＝min{k|k-ASVDTC ofG}为G的邻点可区别的强全色数.本文得到了k≡2(mod 3)时的Xast(Pkn),其中Pn为n阶路.     

折叠立方体网络的最小反馈点集

对简单图G=(V,E),顶点子集F V,如果由V\F导出的子图不含圈,则称F是G的反馈点集。点数最小的反馈点集称图的最小反馈点集,最小的点数称为反馈数。一个k维折叠立方体是由一个k维超立方体加上所有的互补边构成的图。本文证明了k维折叠立方体网络的反馈数f(k)=c.2k-1(k 2),其中c∈k-1     

路和圈多重联图的邻点可区别E-全染色

设G（V,E）是一个简单图,k是一个正整数,f是一个V（G）∪E（G）到{1,2,...,k}的映射.如果u,v∈E（G）,则f（u）=f（v）,f（u）=f（uv）,f（v）=f（uv）,C（u）=C（v）,其中C（u）={f（u）}∪{f（uv）｜uv∈E（G）}.称f是图G的邻点可区别E-全染色,称最小的数k为图G的邻点可区别E-全色数.讨论了路和圈的多重联图的邻点可区别E-全色数。     

竖梯的局部替换图的L(d,1,1)-标号

图的L(d,1,1)-标号定义为顶点集V(G)到非负整数集的映射f,且当d(u,v)=1时,均有|f(u)-f(v)|≥d,当d(u,v)=2,3时,均有|f(u)-f(v)|≥1.不妨设0为最小标号,则称图G的所有L(d,1,1)-标号中的最大跨度max{f(v):v∈V(G)}的最小数为图的L(d,1,1)-标号数,记为λ_d(G).基本给出了竖梯的局部替换图的L(d,1,1)-标号数的确切值或界.