关于图的控制集划分

通过分类归纳的方法,对图的控制集划分问题进行了研究,给出了控制划分数d(G)和全控制划分数d1(G)的上界,并确定了d(Pm×Pn)的所有确切值和d(Cm×Pn)部分的确切值.     

两类图的符号边控制数

对于任意正整数m和n,用I（Cm）表示在长为m圈Cm的每个顶点处增添1条悬挂边而得到的图,I（d（v）-1）（Kn）表示在完全图Kn的每个顶点v处增添（d（v）-1）条悬挂边而得到的图.本文确定了I（Cm）的符号边控制数为0,I（d（v）-1）（Kn）的符号边控制数为1/2（3n-n2）.     

两类乘积图的符号控制数

设G=(V,E)是一个图,一个双值函数f:■,如果对任意顶点v∈V,均有■成立,则称f为图G的一个符号控制函数。图G的符号控制数定义为■为图G的一个符号控制函数}。通过列举图例验证了以往研究中的部分结果是错误的,并重新确定了两类乘积图C_n×P_3和P_n×P_3的符号控制数。     

关于图的符号边控制数的一些结论

设G=（V,E）是一个非空图,一个函数f:E→{-1,1},如果满足∑e’∈N[e ]f（e’）≥1对于每一条边e∈E（G）均成立,则称f为图G的一个符号边控制函数。图G的符号边控制数记为r’_s（G）,定义为r’_s（G）=min{∑e∈E（G） f（e） | f为图G的一个符号边控制函数}。本文对图的符号边控制函数进行了研究,得到了图的符号边控制数的一个新的下界;并且确定了圆梯P₂×C_n的符号边控制数。     

定位-全控制边临界图

给出了正、负定位-全控制边临界图的概念,并着重讨论前者的性质结构,证明了所有树中只有两类图是正定位-全控制边临界图.     

两类图的Fractional控制数

设G=(V,E)为一个图,如果一个实值函数f∶V→[0,1],对任意u∈V(G),均有f(N[u])≥1成立,则称f为图G的一个Fractional控制函数.图G的Fractional控制数定义为γf(G)=min{f(V)|f为图G的一个Fractional控制函数}.本文给出m≥3,n≥2时乘积图Km×Pn的Fra...     

关于图的减边控制

引入了图的减边控制的概念,给出了一个图G的减边控制数γ′m(G)的两个下界,确定了完全图、圈和轮图的减边控制数,并提出了若干未解决的问题和猜想.     

项链图的边度量生成集

图的度量维数问题是组合优化领域研究的一个热点问题,边度量生成集问题是其一个重要变形.给出了项链图的一个边度量生成集,并证明了其边度量维数为3.     

强乘积图与字典乘积图的控制数

证明了:1)图G和H的强乘积图GH的控制数γ(GH)≤γ(G)γ(H),并举例说明此上界是可以达到的;2)若γ(H)=1,则G与H的字典乘积图的控制数γ(G H)=γ(G);若G不含孤立点并且γ(H)≥2,则γ(G H)=γt(G),其中γt表示图的全控制数.     

关于边控制集的一些结论

令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.     

图的符号控制划分数的Nordhaus-Gaddum型结果

设G=(V,E)是一个简单图,在图G的所有符号(全)控制族中,基数最大的符号(全)控制族包含的符号(全)控制函数的数目称为是图G的符号(全)控制划分数.首先给出图的符号控制划分数的Nordhaus-Gaddum型结果,接下来,又给出了图的符号全控制划分数的Nordhaus-Gaddum型结果.     

图的负全控制划分数

定义了图的负全控制划分数,得到了负全控制划分数的存在性和其与边数、最小度的关系,并给出其在部分完全图上的准确值和在一般图上的一个上界。     

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

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

图F_m ▽S_n的边色数和邻强边色数

对图G的一个正常的k边染色法f,若 e∈E(G),e = uv,{f(uw) | uw∈E(G)}≠{f(vw) | vw∈E(G)},则称f为G 的一个k 邻强边染色法,k的最小值称为G 的邻强边色数.V(Fm Sn) = {w}∪{ui | i =1,2,…,m}∪{vij | i =1,2,…,m;j =1,2,…,n},E(Fm Sn) = {wui | i =1,2,…,m}∪{uivij | i =1,2,…,m;j =1,2,…,n}∪{uiui+1 | i =1,2,…,m-1}.　　本文得到了Fm Sn 的边色数和邻强边色数.     

图F_m W_n的边色数和邻强边色数

给出了FmWn的定义,研究了FmWn边染色和邻强边染色,得出了FmWn的边色数和邻强边色数.     

扇图的笛卡儿积的测地数(英文)

对于图G内的任意两点u和v,u-v测地线是指u和v之间的最短路.I(u,v)表示位于u-v测地线上所有点的集合,对于V(G)S,I(S)表示所有I(u,v)的并,这里u,v∈S.G的测地数g(G)是使I(S)=V(G)的点集S的最小基数.文章研究了Pm×Fn和Cm×Fn的测地数,这里Pm表示m阶路,Cm表示m阶圈,Fn表示n阶扇图。     

若干积图的点可区别边染色

证明了:(1)两个n(n2)阶完全图的积图的点可区别边色数为2n. (2)对阶至少是3的完全图Kn,若χ′vd(G)=Δ(G),则χ′vd(G×Kn)=n+Δ(G).(3)若χ′vd(Gi)=Δ(Gi),i=1,2,则χ′vd(G1×G2)=Δ(G1)+Δ(G2).     

单圈图及其与完全图联图的全染色

研究单圈Cn’,一类单圈图G以及它们与完全图Km联图Cn’∨Kn,G∨Kn的全染色问题.借助于已知的完全图全染色的相关引理以及归纳总结的方法得出了Cn’,G的全色数以及其与完全图联图Cn’∨Kn,G∨Kn的全色数,从而验证了对这类图全染色猜想的正确性.