关于图的控制数的新上界

设G=(V,E)是一个图,D■V,如果对任意点v∈V-D,存在u∈D使得uv∈E,则称D为图G的一个控制集,图G的最小控制集的容量称为控制数。通过选点控制的方法,获得了关于控制数的一些重要结论,给出了图的控制数的若干新上界,并推广了一些已知的结果。     

关于圈与完全图的笛卡儿积的测地数

对于图G内的任意两点u和v,在u和v之间的最短路称为u-v测地线.I(u,v)表示位于u-v测地线上所有点的集合,对于S V(G),I(S)表示所有I(u,v)的并,这里u,v∈S.如果I(S)=V(G),那么称S是G的测地集;并把测地集的最小基数称为G的测地数,记为g(G).文章主要研究Cn×K3的测地数.     

新邻域条件与图的上可嵌入性

用NG(u)表示一个图G中任意点u的邻域集,结合图G的邻域条件,主要证明了如下结果:设G是2-连通图,若对G中任意相邻的点u和v,即uv∈E(G),一定存在ai∈NG(u),bi∈NG(v)且ai≠v,bi≠u,使得aibi∈E(G)(i=1,2),则G是上可嵌入的.     

Sm∨Fn的全色数

设G(V,E)是阶数至少是2的简单连通图,k是正整数,若f是从V(G)∪E(G)到{1,2,…,k}的一个映射,使得:对于任意的uv,vw∈E(G),u≠w,有f(uv)≠f(vw);且对于任意的uv∈E(G),u≠v,有f(u)≠f(v),f(u)≠f(uv),f(v)≠f(uv),则称f为G的一个k-全染色(简记成k-TC of G).而χt(G)=min{k|k-TC of G},称为G的全色数.设G和H是点边都不相交的简单图,V(G∨H)=V(G)∪V(H),E(G∨H)=E(G)∪E(H)∪{uv|u∈V(G),v∈V(H)},则称G∨H是G与H的联图.给出m 1阶星和n 1阶扇的联图的全色数.     

Halin图的集染色

对于非平凡连通图G,G的k集染色是指映射c：V（G）→Nk,对任意顶点v∈V（G）,定义邻色集cN（v）={c（u）｜u∈N（v）},若对uv∈E（G）有cN（u）≠cN（v）,则称c为G的一个k集染色.满足上述条件的最小k值称为G的集色数,记为χs（G）.为了更快更有效地给Halin图着色,采用集染色的着色方法,证明了当p≥4时,Halin图G（Cp,Tq）的集色数是3,并且还证明了对任意的Halin图G（Cp,Tq）,有p＋1≤q≤2p-2成立.     

图K_(2n)\E(F_5)(n≥13)的点可区别边染色

对简单图G(V,E),设f是从E(G)到{1,2,…,k}的映射,k为自然数,如果f满足:1)对任意的uv,uw∈E(G),v≠w,有f(uv)≠f(uw);2)对任意的u,v∈V(G),u≠v,有C(u)≠C(v).则称f为图G的k-点可区别边染色法,而最小的k被称为点可区别边色数(其中C(u)={f(uv)|uv∈E(G)}).研究了图K2n\E(F5)(n≥13)的点可区别边色数.     

图K2n\E（Fm）（n≥4,m≥2）的点可区别边染色

对简单图G(V,E),设f是从E(G)到{1,2,…,k}的映射,k为自然数,如果f满足:1)对任意的uv,uw∈E(G),v≠w,有f(uv)≠f(uw);2)对任意的u,v∈V(G),u≠v,有C(u)≠C(v).则称f为图G的k-点可区别边染色法,而最小的k被称为点可区别边色数(其中C(u)={f(uv)|uv∈E(G)}).研究了图K2n\E(Fm)(n≥4,m≥2)的点可区别边色数.     

连通、几乎局部连通拟无爪图是完全圈可扩的

G是一个图，B（G）表示G中所有局部不连通的点构成的集合。如果B（G）是独立集，并且对任意v∈B(G),Eu∈V(G),使G[N(v)∪{u}]连通，则称G是几乎局部连通的。如果G中所有爪心构成的集合D（G）是独立集，并且对任意v∈D(G),G[N(v)]是强2－控制的，则称G是拟无爪图。本文证明：连通、几乎局部连通的拟无爪图是完全圈可扩的。     

几类图的负对控制数

设D V是图G=(V,E)的任意一个对控制集,如果一个函数f:V→{-1,0,1}满足条件1)对任意点v∈D,有f(v)=1,对任意点v∈V-D,有f(v)≤0,2)对任意点v∈V,均有f(N[v])≥1,则称函数f为图G的负对控制函数。负对控制函数f的重量f(V)是V中所有点的函数值之和,图G的负对控制数γp-(G)=min{f(V)|f是图G的负对控制函数}。本文研究一些图的负对控制数。     

关于边控制集的一些结论

令G＝（V，E）是一个图，M是边集E（G）的子集，如果有e∈E（G）／M，e至少与M中一条边相连，则称M为图G的边控制集，进一步，若M是匹配，则称M为图G独立边控制集，本文给出关于边控制集的一些结论。（1）设图H，S是两中连勇图，且H,S∈ж，γe(S)=1,M和M′＝｛uv｝分别是图H和S的唯一最小边控制集，其中S是图1中的（G1，G2，G3，G4）四个图之一，对任何点x∈V（S）＝｛u,v｝,y∈V(H)-V(M),令G＝H（y=s)S，则G∈ж，（2）如果连通图G≠K2，G∈ж，γe(G)=k,则存在G的两个连通于图H，S和某两个正整数l,m使H∈ж，S∈ж，且γe(H)=k-l,γe(S)=l,G≌H（yi=xi)S,其中l≤i≤m.     

点可区别边色数的一个上界

设G是简单图,f是从V(G)∪E(G)到{1,2,…,k]的一个映射.对每个u∈V(G),令C(u)={f(uv)|v∈V(G),uv∈E(G)].如果f是k-正常边染色,且对任意u,v∈V(G),有C(u)≠C(v),那么称f为图G的点可区别边染色(简称为k-VDEC).数x's(G)=min{k|G有k-VDEC}称为图G的点可区别边色数.本文通过应用概率方法,证明了对任意最大度△≥2的图G,x's(G)≤16△.     

图S_m∨F_n,F_m∨F_n与W_m∨F_n的第一类弱全色数

对简单图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);则称f是G的第一类弱全染色.给出了星与扇,扇与扇,轮与扇联图的第一类弱全色数.     

关于图的负对控制数的界

设D真包含V是图G=(V，E)的任意一个对控制集。如果一个函数f：V→{-1，0，1}满足条件：(1)对任意点u∈D，有f(v)=1，对任意点v-D，有f(v)≤0；(2)对任意点v∈V，均有f(N[v])≥1；则称函数f为图G的负对控制函数。负对控制函数f的重量f(V)是v中所有点的函数值之和，图G的负对控制数γp^-(G)=min{f(V)|f是图G的负对控制函数}.本文研究了图的负对控制数的界。     

Pm∨Sn的点可区别全色数

设G是简单图,f 是从V(G)∪E(G) 到{1,2,…,k}的一个映射.对每个u∈V(G),令C(u)={f(u)}∪{f(uv)|v∈V(G),uv∈E(G)}.如果f是k-正常全染色,且对任意u,v∈V(G),有C(u)≠C(v),那么称f为图G的点可区别全染色(简称为k-VDTC).数χv t(G)=min{k|G有k-VDTC}称为图G的点可区别全色数.给出m阶路Pm和n 1阶星Sn的联图的点可区别全色数.     

图的最小符号控制函数的充要条件

在图G=（V,E）的顶点集V上定义一个二值函数f=V→{-1,1},使对任何v∈V,f(N[v])≥1,则称f是图G的一个符号控制函数。图的符号控制函数的权重定义为f(V)=∑v∈vf(V),它的最小权重称为图的符号控制数,记为γs(G）达到最小权重的符号控制函数称为图的最小符号控制函数,本文讨论最小符号控制函数的必要条件。     

关于P_(2r,2s-1)的k-优美标号

对于简单图G=,如果存在一个映射f:V(G)→{0,1,2,…,|E|+k-1}满足:1)对任意的u,v∈V,若u≠v,则f(u)≠f(v);2)max{f(u)|u∈V}=|E|+k-1;3)对任意的e1,e2∈E,若e1≠e2,则g(e1)≠g(e2),且{g(e1)|e∈E}={k,k+1,…,|E|+k-1},g(e2)=|f(u)-f(v)|,e=uv,则称G是k-优美图,f称为G的k-优美标号.作者研究了一类图的k-优美标号.     

完全多部图的符号罗马控制数

设图G=(V,E)是一个简单无向图,若实值函数f:V→{-1,1,2}满足以下两个条件:(i)对于任意v∈V,均有∑_(u∈N[v])f(u)≥1成立;(ii)任意v∈V,若f(v)=-1,则存在一个与v相邻的顶点u∈V,满足f(u)=2,则称该函数为图G的符号罗马控制函数.定义图的符号罗马控制数为γSR(G)=min{f(V)f是图G的符号罗马控制函数}.通过对完全多部图中的顶点数进行分类,给出了当k≥3时,完全多部图K(n_1,…,n_i,…,n_k)的符号罗马控制数的准确值.     

容错定位控制集的界

给定图G=(V,E),S是V的任意一个非空子集,如果对所有的v∈V-S,集合I(v)=N［v］∩S都是非空且是两两不同的, 那么称S是G的一个定位控制集.如果当S中所有的装置都传送正确的监测信息值0,1或2,或者仅有一个装置错误地传送数值0而不是1或2时,它都能测定出V中任何一个错误的处理器w,那么称S是G的一个容错定位控制集.研究了容错定位控制集,给出了容错定位控制集在几类有限图和无限三角形格子图中的一些界.     

C_m×K_n的邻点可区别全染色

设G(V,E)是阶数至少为2的简单连通图,k是正整数,V∪E到{1,2,3,…,k}的映射f满足:对任意uv,vw∈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),有C(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).本文得到了圈Cm和完全图Kn的笛卡尔积图Cm×Kn邻点可区别的全色数.     

扇、轮和完全图的多重联图的邻点可区别E-全染色

G(V,E)是一个简单图,k是一个正整数,f是一个V(G)∪ E(G)到{1,2,…,k}的一个映射.如果(A)u,v∈V(G),则f(u)≠f(v),f(u)≠f(uv),f(v)≠f(uv),C(u)≠C(v),其中C(u)={f(u)}∪{f(uv)∣u,v∈E(G)},称f是图G的邻点可区别E-全染色,称最小的数k为图G的邻点可区别E-全染数.文章讨论了扇与轮、完全图的多重联图的邻点可区别E-全色数.