直径为4的奇优美树

对于简单图G=, 如果存在一个映射f: V→{0,1,2,...,2E|-1}满足:对任意的u,v∈V,若u≠v,则f(u)≠f(v);max{f(v)|v∈V}=2|E|-1;对任意的e1,e2∈E,若e1≠e2,则g(e1)≠g(e2),此处g(e)=|f(u)-f(v)|,e=uv;{g(e)|e∈E}={1,3,5, ...,2|E|-1},则称G为奇优美图,f 称为G的奇优美标号.提出一个猜想:每棵树都是奇优美的,文章证明了直径为4的树都是奇优美的.     

P_m∨S_n的点可区别全色数

设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的联图的点可区别全色数.     

笛卡尔乘积和直积图的全{k}控制划分数（英文）

给定正整数k,不含孤立点的图G的全{k}控制函数(T{k}DF)是从顶点集V(G)到{0,1,2,…,k}的映射f使得对任意的v∈V(G),与v相邻的点在f下的赋值之和至少为k.若元素两两不同的全{k}控制函数集合{f_1,f_2,…,f_d}满足d∑i=1f_i(v)≤k对任意v∈V(G),则称该集合为G的全{k}控制族(T{k}D族).含有函数最多的G的全{k}控制族的函数数量成为全{k}控制划分数,记为d_t~({k})(G).2013年,Aram等提出了以下问题:是否当4nmk时d_t~({k})(C_m□C_n)=3,当4nmk时d_t~({k})(C_m□C_n)=4.这里证明了当4nmk且k≥2或4nmk且2nk时d{k}t(C_m□C_n)=3.该结论部分回答了上述问题.更进一步,确定了路和圈、路和路、圈和圈的全{k}控制划分数.     

一类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))的关联邻点可区别全色数.     

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

G(V,E)是一个简单图,k是一个正整数,f是V(G)∪E(G)到{1,2,…,k}的一个映射.如果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的邻点可区别E-全染色,称最小的数k为图G的邻点可区别E-全色数.得到路和圈的联图的邻点可区别E-全色数.     

关于图的正交[0,ki]m1-因子分解

设k1,...,km是正整数,若对每个x∈V(G)有dG(x)≤k1+...+km-m+1,H是G的一个m-{m1-星,...,mn-星}-子图,则图G有一个[0,ki]m1-因子分解与H正交.     

C_m·P_n的D(3)-点可区别边色数

对阶数不小于3 的连通图G(V,E),设α,β为正整数,令映射f:Ef{1,2,...,α},若{u,v}∈V(G),1≤d(u,v)≤β,有C(u)≠C(v) 则称f为G的一个α -D(β)-点可区别的边染色,简记为α -D(β)-VDPEC,对一个图进行α -D(β)-点可区别的边染色,所需的最小的α称为图G的D(β)-点可区别的边色数,记为χ′β-vd(G),其中d(u,v)表示两个点之间的最短距离.得到Cm·Pn的D(3)-点可区别边色数.     

数列{K(u,v)=2uv-u-v}的若干性质

本文给出了数列{K(u，v)=2uv-u-v}的一些性质,对数列{N(u,v)=2w u v}作了进一步研究。     

Mycielski图的一般邻点可区别全色数

设图G(V,E)是阶数至少为2的简单连通图,k是正整数.从V∪E到{1,2,…,k}的映射f称为图G的一般邻点可区别全染色(简记k-GAVDTC),如果对任意2个相邻顶点u≠v的色集合C(u)≠C(v),其中C(u)={f(u)}∪{f(uv)|uv E(G)},并称χgat(G)=min{k|G有k-GAVDTC}为图G一般邻点可区别全色数.综合运用构造法、调整法及概率法讨论了路、圈、扇、星、轮和完全二部图的Mycielski图的一般邻点可区别全染色,给出了其确切的一般邻点可区别全色数.     

两类树图的Hamiltonian色数

一个n阶连通图G的Hamiltonian染色是从G的顶点集V(G)到正整数集N(称为颜色集)的一个映射c,使得对于G的任意2个不同的顶点u和v满足|c(u)-c(v)|+D(u,v)≥n-1,其中D(u,v)表示G中u到v的最长路径的长度。对一个Hamiltonian染色c,将max{c(u):u∈V(G)}称为c的值,记作hc(c)。将min{hc(c):c是G的任意Hamiltonian染色}称为G的Hamiltonian色数,记作hc(G)。本次研究得到了满足max{D(u,v)|u,v∈V(G),u≠v}≤n/2的d-重似星树和广义双星这两类树图的Hamiltonian色数的确切值。     

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

图的色数与其补图边色数的关系

本文对图的点色数与其补图边色数的关系进行了考察.     

图上的对策着色和对策着色数

图G的对策色数Ⅱχg(G)是由图的点色数χg(G)拓展而来的.本文对几类特殊的图进行了讨论,分别给出了图Qn,Gn以及与圈有关图的对策色数Ⅱ,并给出了选手Alice相应获胜的对策.     

几种图的对策着色和对策色数

介绍了一种新的色对策和对策色数,比较了2种色对策的差异.对几种特殊的图形的色对策数进行了讨论,运用顶点标号方法,给出获胜策略.     

超图的分数着色研究

图的分数着色问题是分数图论中的一个重要研究课题之一，超图作为图的推广在实际中有着广阔的应用．本文将一般图中分数着色的几个重要结论推广到超图，并证明其正确性。     

幂图的邻点可区别全色数和邻点可区别-VE全色数

根据路的幂图Pkn的结构性质,用穷染、递推的方法,讨论了Pkn的邻点可区别全染色和邻点可区别-VE全染色,得到了相应的色数,并给出了一种染色方案.     

SmVPn的邻点可区别全色数

设G的阶数不小于2的简单连通图。G的k-正常全染色称为是邻点可区别的，如果对G的任意相邻的两顶点，其点的颜色及关联边的颜色构成的集合不同。这样的k中最小者称为G的邻点可区别全色数。本文主要是给出了星图和路的联图的邻点可区别全色数，并提出了一猜想。     

图的范畴积的圆色数

图的圆色数的定义是图的色数的一个自然的推广,它是由Vince首先提出的,本文主要研究图的范畴积的圆色数.     

图S_m∨W_n的点可区别边色数

对图G的正常边染色,若满足不同点的点所关联边色集合不同,则称此染色法为点可区别的边染色法,其所用最少染色数称为该图的点可区别边色数。研究得到了Sm∨Wn的点可区别边色数。     

Sm∨Pn的邻点可区别全色数

设G的阶数不小于2的简单连通图.G的k-正常全染色称为是邻点可区别的,如果对G的任意相邻的两顶点,其点的颜色及关联边的颜色构成的集合不同.这样的k中最小者称为G的邻点可区别全色数.本文主要是给出了星图和路的联图的邻点可区别全色数,并提出了一猜想.