没有5-圈的平面图的BB-染色

设H为G的一个生成子图,（G,H）的一个BB-k-染色是指一个映射f：V（G）→{1,2,…,k},当uv∈E（H）,｜f（u）-f（v）｜≥2;当uv∈E（G）／E（H）,｜f（u）-f（v）｜≥1.定义（G,H）的BB色数x_b（G,H）为最小的整数k,使得（G,H）是BB-k可染的.本文研究了对于任意的连通,非二部平面图G,且G没有5-圈,都存在一棵生成树T,使得x_b（G,T）=4.     

L（j,k）-number of Direct Product of Path and Cycle

For positive numbers j and k, an L(j,k)-labeling f of G is an assignment of numbers to vertices of G such that |f(u)-f(v)|≥j if uv∈E(G), and |f(u)-f(v)|≥k if d(u,v)=2. Then the span of f is the difference between the maximum and the minimum numbers assigned by f. The L(j,k)-number of G, denoted by λj,k(G), is the minimum span over all L(j,k)-labelings of G. In this paper, we give some results about the L(j,k)-number of the direct product of a path and a cycle for j≤k.     

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阶路.     

一类3-正则图的邻强边染色

对简单图G(V,E),f是从V(G)∪E(G)到{1,2,…,k}的映射,k是自然数,若f满足(1)uv,uw∈E(G),u≠w,f(uv)≠f(uw);(2)uv∈E(G),C(u)≠C(v).则称f是G的一个邻强边染色,最小的k称为邻强边色数,其中C(u)={f(uv)|uv∈E(G)}.给出了一类3-正则重圈图的邻强边色数.     

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

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

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

设G(V,E)是简单图,k是正整数.从V(G)∪E(G)到{1,2,…,k}的映射f被称作G的邻点可区别-点边全染色,当且仅当:■uv∈E(G),f(u)≠f(uv),f(v)≠f(uv),■uv∈E(G),C(u)≠C(v),且称最小的数k为G的邻点可区别-点边全色数.其中C(u)={f(u)}∪{f(uv)|uv∈E(G)},研究了一些联图的邻点可区别-点边全染色法,得到了它们的色数.     

联图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的全色数．     

优美图的一些性质

对于一个(p,q)-图G,如果存在一个单射.f:V(G)→{0,1,…,q},使得边标号集合{f(uv)| uv∈E(G)}={1,2,…,q},其中边标号为f(uv)=|f(u)-f(v)|,那么称G是优美图,并称.f是G的一个优美标号.通过研究若干优美图,得出一些优美图的性质.     

图带宽和与其对偶超图带宽和的关系

设H=（E1,E2,…,Em）是集合X上的一个超图,一个1-1映射f:X→{1,2,…,|X|}称为H的一个标号,对H的任一标号f,BS（H,f）=∑(E∈H)max{|f(u)-f(v)|;u,v∈E}称为超图H的关于标号f的带宽和BS(H)=min{BS(H,f)|f是超图H的标号|}称为H的带宽和．论文研究图带宽和与其对偶超图的带宽和这两个参数间的关系．     

关于P（n1,n2,...nm）和Dm,4的优美性

一个简单图G=(V,E)是k-优美的(k≥1的整数),如果存在一个1-1映射 f:V(G)→(0,1,…,|E| k-1)使得对所有的边e=wv∈E(G),由f~*(u,v)=|f(u)-f(v)|导出的映射 E(G)→{k,k 1,…,|E| k-1}是一个1-1对应。这个关于k-优美的概念是由Slater和Thuillier相互独立地提出来的。当k=1,就是我们通常研究的优美图。显然,k-优美图一定是1-优美图。反之不真。例如,三回路c_3是1-优美图,但对k>1,非k-优美。     

路和圈多重联图的邻点可区别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-全色数。     

一类多重联图的邻点可区别E-全染色

设G（V,E）是一个简单图,k是一个正整数,f是一个V（G）∪E（G）到{1,2,…,k]．的映射．如果Au,v∈E（G）,则f（u）≠f（v）,f（u）≠f（uv）,f（v）≠f（uv）,C（u）≠C（v）,其中C（u）={f（u））U{f（uv）｜uv∈E（G））．称f是图G的邻点可区别E-全染色,称最小的数k为图G的邻点可区别B全色数．本文给出了星、路、圈间的多重联图的邻点可区别E-全色数．     

某些中间图的邻点可区别E-全色数

设G（V,E）是简单连通图,T（G）为图G的所有顶点和边构成的集合,并设C是k-色集（k是正整数）,若T（G）到C的映射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的邻点可区别E-全染色（简记为k-AVDETC）,并称χ_（at）~e（G）=min{k｜图G有k-邻点可区别E-全染色}为G的邻点可区别E-全色数.图G的中间图M（G）就是在G的每一个边上插入一个新的顶点,再把G上相邻边上的新的顶点相联得到的.探讨了路、圈、扇、星及轮的中间图的邻点可区别E-全染色,并给出了这些中间图的邻点可区别E-全色数.     

Pm×Kn的邻点可区别全色数

设G是简单图．设f是一个从V(G)∪E(G)到{1,2,…,k}的映射．对每个v∈V(G),令C_f(v)={f(v)}∪{f(vw)|w∈V(G),vw∈E(G)}．如果f是k-正常全染色,且对任意u,v∈V(G),uv∈E(G),有C_f(u)≠C_f(v),那么称f为图G的邻点可区别全染色(简称为k-AVDTC)．数x_(at)(G)=min{k|G有k-AVDTC}称为图G的邻点可区别全色数．本文给出路P_m和完全图K_n的Cartesion积的邻点可区别全色数．     

关于D(F_n)和D(W_n)的点关联邻点可区别全色数

对简单图G(V,E),f是从V(G)∪E(G)到{1,2,…,k}的映射,k是自然数,若满足:1)uv,uω-∈E(G),v≠,-ωf(uv)≠f (uω-);2)uv∈E G,C(u)≠C(v).则称f是G的点关联邻点可区别全染色法,其所用到的最少颜色数称为图G的点关联邻点可区别全色数.这里C(u)=f(u)∪f(uv)uv∈E(G).得到了扇和轮的倍图的点关联邻点可区别全色数.     

折叠立方体图的邻点可区别全色数

简单图G的全染色是指对G的点和边都进行染色．称全染色为正常的如果没有相邻或关联元素染同一种颜色．简单图G=（VE）的正常全染色^称为它的邻点可区别全染色如果对任意两个相邻顶点u、v,有H（u）≠H（v）,其中H（u）={（u））U{^（uw）｜uw∈E（G））而H（v）={h（u）}U{h（vx）｜vx∈E（G））．G...     

本刊英文版Vol.29(2013),No.8论文摘要(英文)

<正>L(j,k)-number of Direct Product of Path and Cycle Wai Chee SHIU Qiong WU Abstract For positive numbers j and k,an L(j,k)-labeling f of G is an assignment of numbers to vertices of G such that |f(u)-f(v)|≥j if uv∈E(G),and |f(u)-f(v)|≥k if d(u,v)=2.Then the span of f is the difference between the maximum and the minimum numbers assigned by f.The L(j,k)-number of G,denoted byλ_(j,k)(G),is the minimum span over     

轮与星的多重联图的邻点可区别E-全染色

G(V,E)是一个简单图,k是一个正整数,f是一个V(G)UE(G)到{1,2,…,k}的映射.如果■u,v∈V(G),则f(u)≠f(v),f(u)≠f(uv),f(v)≠f(uv),C(u)≠C(v),称f是图G的邻点可区别E-全染色,称最小的数k为图G的邻点可区别E-全色数.给出了轮与星的多重联图的邻点可区别E-全色数.     

二分（0，mf—m＋1）-图的正交（0，f）-因子分解

设G=（X,Y,E（G））是一个二分图,分别用V（G）=X∪Y和E（G）表示G的顶点集和边集．设f是定义在V（G）上的整数值函数且对任意x∈V（G）有f（x）≥k．设H1,H2,…,Hk是G的k个顶点不相交的子图,且｜E（Hi）｜=m,1≤i≤k．本文证明了每个二分（0,mf—m＋1）．图G有一个（0,f）-因子分解正交于Hi（i=1,2,…,k）