图的强直积的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-距离色数。     

笛卡尔积图的2-距离色数

图G(V,E)的2-距离染色是指正常的顶点染色,且距离不大于2的任意两个顶点着不同的颜色.给出了笛卡尔积图的一个2-距离色数的可达界,即Δ(G) Δ(H) 1≤χ2(G×H)≤2χ(G)χ2(H),以及一些特殊笛卡尔积图的2-距离色数,说明此界可达.     

完全立方Halin图的2-距离着色

图G的2-距离着色是正常的顶点着色,并且使G中距离不大于2的任意两个顶点着不同的颜色.图G的2-距离色数是图G的所有2-距离着色中所用色数的最小者,记为χ2d(G).探讨了完全立方Halin图Hn的2-距离着色,并得χ2d(H0)=4,5≤χ2d(Hn)≤6(n≥1).     

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

证明了:(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).     

图的一般邻点可区别色指标

给出了完全图Kn、路Pm与完全图Kn的Cartese积Pm×Kn、圈Cm与Kn的Cartese积Cm×Pn等图的一般邻点可区别色指标,并得到2维网格Mm,n2种颜色可染、2维环形网格TMm,n3种颜色可染等结论.     

图的某些[r,s,t]-染色的色数

证明了(1)若图G是二部图,则当r≥s(χ’(G)-1)+2时,χr,s,1(G)=χr,0,0(G);(2)若图G是非二部图,则当r≥sχ’(G)/χ(G)-s+1且r不是s的倍数时,χr,s,1(G)=χr,0,0(G);(3)当Δ(G)≥2,χ’(G)=Δ(G),且s≥2r,r≥2t时,χr,s,t(G)=χ0,s,0(G);(4)当χ’(G)=Δ(G)+1且s-t≥r≥t时,χr,s,t(G)=χ0,s,0(G)。     

非连通并图的优美标号研究

设图G3是长度为3的圈C3或为含3个顶点的路P3,文章给出了非连通图(G3∨Km)∪Kn,t和(G3∨Km)∪Pn,并证明了对任意正整数m,n,t,如果min{n,t}≤m,则图(G3∨Km)∪Kn,t是优美图;如果2≤n≤2m+1,则图(G3∨Km)∪Pn是优美图;同时证明了对任意正整数m,n,图(G3∨Km)∪St(n)和(G3∨Km)∪W2n+5是优美图.其中,Pn是n个顶点的路,G1∨G2是图G1与G2的联图,Km是m个顶点的完全图,m是Km的补图,Kn,t是具有二分类(X,Y)的完全偶图,且|X|=n,|Y|=t,St(n)是具有n+1个顶点的星形树,Wn是具有n+1个顶点的轮图.     

Sierpiński Gasket图的2-距离着色

运用群论中置换的思想,通过置换顶点的着色法,研究Sierpiński gasket图Sn的2-距离着色,且给出了Sierpiński gasket图Sn的2-距离色数的精确值为χ(Sn)=6,其中n≥2.     

稀疏图平方图的染色数上界

图G的平方G2定义为顶点集V(G)=V(G²), 并且uv∈E(G²)当且仅当u和v之间的距离至多为2. G²的色数χ(G²)是指使得G²存在正常k顶点染色的最小整数k. 用权转移的方法证明: 如果mad(G)<4且Δ(G)≥7, 则χ(G²)≤3Δ(G)+1;  如果mad(G)≤4且Δ(G)≥8, 则χ(G²)≤3Δ(G)+5.     

若干联图Pm∨Gn的邻点可区别E-全染色

记χat'e(G)为图G的邻点可区别E-全色数.若Pm是m阶的路,Sn是n+1阶的星,且nm≥2,则χate(Pm∨Sn)=4;若Pm是m阶的路,Fn是n+1阶的扇,且m≥2,n≥2,则χate(Pm∨Fn)=5;若Pm是m阶的路,Wn是n+1阶的轮,且m≥2,n≥3,如果n≡0(mod 2),则χate(Pm∨Wn)=5,如果n≡1(mod 2),则χate>(Pm∨Wn)=6;若Pm是m阶的路,Kn是n阶完全图,且n≥4,m≥2,则χate+(Pm∨Kn)=n+2.     

无K4-子式图的2-距离和可区别边染色

图G的一个正常边染色φ若满足:∠u,v∈V(G),且d_G(u,v)≤2都有f(u)≠f(v),其中f(u)=∑_uw∈E(G)φ(uw),则称φ为图G的2-距离和可区别边染色。运用反证法,结合构造染色函数法,研究了无K₄-子式图的2-距离和可区别边染色,确定了无K₄-子式图的2-距离和可区别边色数的一个上界。     

平面图是(Δ+2)-2-距离着色的充分条件

主要得到了围长至少6,最大度至少12的平面图是(Δ+2)-2-距离着色的1个充分条件.     

三角形函数下的概率2－距离空间

提出了三角形函数下的概率２－距离空间的概念，证明了在弱连续三角形函数下强邻城系．Ｎ诱导出Ｈａｕｓｄｏｆｆ拓扑，从而推广了［１］中主要定理２．１１及［２］中定理１２．１．     

基于修正的χ2-距离散度的不确定概率约束优化

许多有重要价值的实际问题的数学模型为不确定性概率优化模型,如决策问题等,该类模型常存在分布的不确定性。研究了基于修正的χ2‐距离散度的不确定概率优化问题,构造了基于修正的χ2‐距离散度的不确定集,对模型内部极大化问题进行求解。研究了最坏情况下的概率函数,用测度变换的方法把一个关于分布 P的优化问题转化为关于似然比瞊（ξ）的凸优化问题;应用凸优化问题的对偶理论,证明了拉格朗日对偶问题的等价性,并且得到了不确定概率优化问题的等价形式。     

最大度为5的平面图的2-距离列表染色

讨论了最大度为5的平面图G的2-距离列表染色问题.给出了图G的2-距离列表色数χl2(G)的一些性质:1)若g(G)≥6,则χl2(G)≤11;2)若g(G)≥7,则χl2(G)≤9;3)若g(G)≥8,则χl2(G)≤8.其中,g(G)为图G的围长.     

L距离及其应用

文中定义了L距离，讨论了它的性质，指出了应用L距离对高校教师学术水平进行聚类分析的合理性。