图的L(p,q)-标号问题

令G为图,p,q为2个正整数,p≥q。G的一个L(p,q)-标号是映射f:V(G)→{0,1,2,…},使得对任意x,y∈V(G),若dG(x,y)=1则|f(x)-f(y)|≥p;若dG(x,y)=2则|f(x)-f(y)|≥q。G的一个m-L(p,q)-标号是标号f:V(G)→{0,1,2,…},使得对任意x∈V(G),有f(x)≤m。并称λp,q(G)=min{m|存在G的一个m-L(p,q)-标号}为图G的L(p,q)-数。本文给出k-退化图、G1和G2的联图G1∨G2及G1和G2的M-matched sum图G1M G2的L(p,q)-数不同上界。最后给出仙人掌图,唯一圈图L(p,1)-数λp,1(G)的可达界。     

两类并图的优美标号

讨论2n个优美二分图与一条通路并的优美性,得到如下结论:设二分图G=(X,Y,E)优美,优美标号为θ,边数为q,a=max{k|0相似文献   

s不超过6的无标号(n,n/2+s)-奇图的计数

一个图称为(n,m)-图,若|V(G)|=n且|E(G)|=m.一个奇图是指每个点的度都是奇数的图.给出了一种新的图同构的定义,计算并给出了不同构无标号(n,n/2+5)-奇图的结果,并对s=4,6给出了不同构无标号(n,n/2+s)-奇图的完整结果.     

一类连通可满着色图的L(2,1)标号

令G=(V(G),E(G))是一个简单图,Mp(G)为图G的广义Mycielski图.图G的L(2,1)标号数记作λ(G),定义为λ(G)=min{k|G有一个k-L(2,1)标号}.一个连续的L(2,1)标号是一个L(2,1)标号,使得所用的标号是连续的,相应的标号数记作-λ(G).凡是满足λ(G)=-λ(G)的图称为可满着色图.给出了一些特殊图的广义Mycielski图的L(2,1)标号数,从中发现一些广义Mycielski图为可满着色图,并由此猜想广义Mycielski图(除Mp(Kn)之外)为可满着色图.     

2a3bpcqd(p≡1(mod q))阶单群

运用单群分类定理,给出了阶为2a3bpcqd(p≡1(modq))的所有K4-单群,从而,给出了p≡1(modq)(p是|G|的最大素因子,q是|G|的次大素因子)的所有K4-单群.     

外部平面图的L(p,q)-标号

对于正整数p,q,n与图G,如果函数φ:V(G)→｛0,1,2, ,n｝满足如下关系:若distG(u,v)=1,则|φ(u)-φ(v)|≥p;若distG(u,v)=2则|φ(u)-φ(v)|≥q,那么称函数φ为图G的L(p,q) 标号.在所有L(p,q) 标号中最小的n称为(p,q) 跨度,记作λ(G;p,q).本文证明了如下结论:设图G是一个最大度为Δ的外部平面图,那么λ(G;p,q)≤qΔ+4p+2q-4.     

图的联结数与分数[a,b]-因子存在性

设G是一个简单无向图,G的联结数定义为bind(G)=min|NG(X)||X|:Ф≠X V(G),NG(X)≠V(G)研究了图的联结数bind(G)与图的分数[a,b]-因子之间的关系,给出了图有分数[a,b]-因子的若干充分条件.     

两类n+3阶n色的色唯一图

用Tn(a,b,c)表示完全图Kn及其外一边uw作一些边后得到图,使|N(u)∩V(Kn)|=a,|N(w)∩V(Kn)|=b,|N(u)∩N(w)∩V(Kn)|=c.Tn(a,b,c)的边uw剖分一个顶点v得到的图为Fn(a,b,c).研究Fn(a,b,c)的色性问题,并给出Fn(a,b,c)是色唯一图的两个充分条件.     

关于链路P_n(m_1,m_2,…,m_(n-2))的k-优美性

图G的标号是指G的顶点集到一个整数集的映射g,且对e=uv∈E(G)由g(u)和g(v)诱导出边e的标号.本文给出了链路P_n(m_1,m_2,…,m_(n-2))的k-优美标号.即证明了图P_n(m_1,m_2,…,m_(n-2))是k-优美图.进而推广了原有的一些结果.     

无K_(1,t)图的L(d,1)-T标号

给定一个连通图G=(V,E)及其一棵支撑树T,图G的一个L(d,1)-T标号即函数g:V(G)→{0,1,2,…},满足:(1)如果xy∈E(G),则|g(x)-g(y)|≥1;(2)如果dG(x,y)=2,则|g(x)-g(y)|≥1;(3)如果xy∈E(T),则|g(x)-g(y)|≥d.假设图G有一个L(d,1)-T标号函数g:g(V){0,1,2,…,k},则图G的所有L(d,1)-T标号函数中最小的整数k记为L(d,1)-T标号数λdT(G,T).本文证明了若G是无K1,t(3≤t≤n)的连通图,其最大度为Δ,|G|=n,T为G的任意支撑树,则λdT(G,T)≤tt--12Δ2+Δ+2d-2.     

Halin图的列表L(p,q)标号

图G的一个列表L,是指对G的每一个顶点v指定的一个标号集合L(v)。G的一个列表L(p,q)-标号是G的一个正常L(p,q)-标号,使得每一个顶点v∈V(G)均可在其对应的列表L(v)里选取一个标号。G的一个k-列表L(p,q)标号是一个列表L(p,q)-标号,使得G的所有顶点v的列表L(v)的长度L(v)=k 1。定义G的列表L(p,q)-标号数λl(G)=m in{G k有一个k-列表L(p,q)-标号}。讨论了Halin图的列表L(p,q)-标号问题,证明了λl(G;p,q)≤(2q-1)Δ(G) 6p-3。     

最小度和[a,b」——覆盖图

设 a≤ b是整数,G=(V(G),E(G))是一个图G的一个支撑子图F称为G的一个[a,b]—因子,若对任意的v∈V(G),有a≤d_F,(v)≤b.图G称为是[a,b]—覆盖图,若对G的每一条边,存在G的一个[a,b]）—因子包含它,本文给出了一个图是[a,b]—覆盖图的关于最小度的充分条件,证明了下列结果;设1≤an (a b)-2(bn-1)~(1/2)则G是一个[a,b]—覆盖图.     

高度平面图的列表L(p,q)-标号

如果平面图G的最大度Δ(G)=|V(G)|-k, k=1,2,…,则称G为一个hk-图,k=1,2的hk-图称为高度平面图.研究了高度平面图G的列表L(p,q)-标号问题, 给出了高度平面图G的列表L(p,q)-标号数λl(G;p,q)的上界,并对h1-图证明了λl(G;p,q)≤(2q-1)Δ 6(p-q);对h2-图有λl(G;p,q)≤(2q-1)Δ 8p-6q-1.     

关于2G与路的并的优美标号

设G是有q条边的优美二部图,优美标号为θ,pm是有m条边的简单路,C=k 0〈k〈q,k≠θ（v）,v∈V（G{）},a=maxC,b=minC,h=min q-a＋2,b{}＋2.图G∪G∪Pm是两个图G与一条简单通路的不交并.证明了：当m=1或m≥h时,图G∪G∪Pm是优美的.应用此结论,得到：对所有的s≥2,t≥2,当m=1或m≥3时,图Ks,t∪Ks,t∪Pm是优美的.     

几类特殊图的一般指标集

令G=(V(G),E(G))为一简单连通图,V(G)和E(G)分别是图G的顶点集和边集.一个顶点标号函数f:V(G)→Z2诱导出一个边标号函数f*:E(G)→Z2,其中?v1 v2∈E(G),有f*(v1v2)=f(v1)+f(v2).当标1和标0的顶点数相差m(m<|V(G)|)时,标号为1和0的边数差的集合称为图G...     

图的几种N(p,q)标号问题

本文给出了图的两个关于点的邻域限制标号的定义:非完全邻域限制标号SN(p,q)与完全邻域限制标号TN(p,q)。SN(p,q)标号是仅对图的大度点的邻域做限制的正常标号;TN(p,q)标号是对图的所有点的邻域做限制的正常标号。图G的非完全邻域限制标号数与完全邻域限制标号数分别记为SL_p,q(G),TL_p,q(G)。本文主要给出了某些图G的SL_p,q(G),TL_p,q(G)的界。     

几种正规积图的带宽

引言设G是个图,V(G)是G的顶点集,E(G)是G的边集。|V(G)|=n,如所周知,任一个1—1对应的函数f:V(G)→{1,…,n}均称为V(G)(或G)上的一个标号。规定f的带宽为B(f)=max{|f(u)-f(V)|:uv∈E(G)},而图G的带宽的定义则是B(G):min{B(f):f是G上的标号}。例如,图1即给出了一个很简单的图G_0的两种不同的标号:     

拟Mobius梯子的L(1,1,1)-标号

图G的一个L(1,1,1)-标号是从顶点集V(G)到非负整数集的一个映射f,且当距离d(u,v)=1,2,3时,均有|f(u)-f(v)|≥1;其中,u,v是图G的顶点.不妨设0为最小标号,则称图G的所有L(1,1,1)-标号中的最大跨度的f(v)最小数为图G的L(1,1,1)-标号数,记为λ_(1,1,1)(G).给出了拟Mobius梯子的L(1,1,1)-标号数的确切值或上下界.     

两个完全图的匹配和的L(p,q)-标号

设p,q为两个非负整数,一个图G的L(p,q)-标号是一个从G的顶点集V(G)到一个非负整数集的映射f,使得对于G中的任意两个顶点u,v,当d(u,v)=1时,|f(u)-f(v)|≥p;当d(u,v)=2时,|f(u)-f(v)|≥q;根据p,q之间的关系,给出两个顶点数都是n的完全图的匹配和的L(p,q)-标号数的上界.而当q≤p≤2q时,确定了两个顶点数都是n的完全图的匹配和的L(p,q)-标号数的准确值.     

图的(a,d)-边反幻点标号

设计了一种算法,逐个求解有限点以内的所有简单连通图的(a,d )-边反幻点标号,然后根据标号结果给出了若干针对特殊图和联图的精确算法,针对一般图则给出了一个启发式搜索算法模型. 该算法分为两个部分,第一部分依据定义设置预判函数,对图集中的所有图进行预判,剔除部分无(a,d )-边反幻点标号的图;第二部分求解剩余图集的(a,d )- 边反幻点标号. 特别地,通过预判函数知,当q ≥ p 时,图G ( p,q ) 无(a,2)-边反幻点标号,故利用算法得到了13 个点以内所有树图的(a,2)-边反幻点标号.