共查询到18条相似文献,搜索用时 140 毫秒
1.
侧廓问题是:寻找一个从V(G)到正整数集合{1,2,…,│V(G)│}的一个一一对应,让x∈V(G)∑ (f(x)-min f(y)尽可能小,这里y∈N*(x),N*(x)是x的闭领域.本文提供这个问题的两个结果. 相似文献
2.
设f:V(G)∪E(G)→[k]是图G的一个非正常的k-全染色,令权重 φ(x)=f(x)+∑x∈e f(e)+∑y∈N(x)f(y),其中,N(x)={y∈V(G)|xy∈E(G)}对任意的边uv∈E(G),如果有φ(u)≠φ(v)成立,则称f为图G的一个邻点全和可区别非正常k-全染色.图G的邻点全和可区别非正常全染... 相似文献
3.
G=(V,E)是有限简单连通图,用V(G)和E(G)分别表示G的顶点集和边集.f是一个从V(G)∪E(G)→{-1,1}的函数.f的权重定义为w(f)=∑x∈V(G)∪E(G)f(x).图G的全符号控制函数f:V(G)∪E(G)→{-1,1}是一个对所有的x∈V(G)∪E(G),都满足f[x]≥1的函数,其中f[x]=∑y∈NT[x]f(y).G的全符号控制数γ*s(G)定义为γ*s(G)=min{w(f)│f是G的全符号控制函数}.Cm表示m个顶点的圈,n-Cm表示恰有一条公共边的n个Cm的拷贝.本文给出了n-C4的全符号控制数. 相似文献
4.
5.
《广州大学学报(自然科学版)》2020,(1)
设f:V(G)∪E(G)→{1,2,…,k}是简单图G的一个正常k-全染色.令C(f,u)={f(e):e∈Ne(u)},C[f,u]=C(f,u)∪{f(u)},C2[f,u]=C(f,u)∪{f(x):x∈N(u)}∪{f(u)}. N(u)表示顶点u的邻集,Ne(u)表示与顶点u的相关联的边集合.令C[f; x]={C(f,x); C[f,x]; C2[f,x]},对任意的边xy∈E(G),C[f; x]≠C[f; y]表示C(f,x)≠C(f,y),C[f,x]≠C[f,y],C2[f,x]≠C2[f,y]同时成立.对任意的边xy∈E(G),如果有C[f; x]≠C[f; y]成立,则称f是图G的一个k-(3)-邻点可区别全染色(简记为k-(3)-AVDTC).图G的(3)-邻点可区别全染色中所需最少的颜色数叫做G的(3)-邻点可区别全色数,记为(″3) as(G).文章研究(2,2)-递归极大平面图的(3)-邻点可区别全染色,并确定此类图的(3)-邻点可区别全色数.此外,提出了简单图的(3)-邻点可区别全染色猜想. 相似文献
6.
邵振东 《南京大学学报(自然科学版)》2004,21(2):234-238
图G的L(2,1)-标号是一个从顶点集V(G)到非负整数集的函数f(x),使得若d(x,y)=1,则|f(x)-f(y)|≥2;若d(x,y)=2,则|f(x)-f(y)|≥1.图G的L(2,1)-标号数λ(G)是使得G有max{f(v):v∈V(G)}=k的L(2,1)-标号中的最小数k.本文将L(2,1)-标号问题推广到更一般的情形即L(d1,d2,d3)一标号问题.并得出了一般图和平面图的λd1,d2,d3(G)的上界. 相似文献
7.
《汕头大学学报(自然科学版)》2018,(4)
设G为简单图. G的全k-染色是指k种颜色对图G的全体顶点及边的一个分配.设c是图G的一个全k-染色,任意的x∈V(G),称w(x)=Σx∈ec(e)+Σy∈N(x)c(y)为点x的扩展和,其中N(x)={y∈V(G)|xy∈E(G)}.称图G的全k-染色c为邻点扩展和可区别(简记为NESD),如果w(x)≠w(y),其中xy∈E(G).图G的NESD全k-染色的最小值k被称为图G的邻点扩展和可区别全色数,简记为egndi∑(G).本文探讨了轮,扇,星和双星的邻点扩展和可区别全染色,并得到了它们的邻点扩展和可区别全色数. 相似文献
8.
朱海洋 《宝鸡文理学院学报(自然科学版)》2006,26(1):23-27
令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)的可达界。 相似文献
9.
半无爪图中的几个结果 总被引:3,自引:2,他引:1
若对图G中任意一对距离为2的点x,y,存在u∈N(x)∩N(y),使得N│u│包含于N│x│UN│y│,则称G为半无爪图.本文得到了连通半无爪图点泛圈方面的几个结果,改进了Ainouche和Li MingChu的相关结果. 相似文献
10.
记G=(V,E)是简单图,δ表示图G的最小度,NC=min{|N(x)∪N(y)|:x,y∈V(G)mxt∈E(G)|,NC2=min{|N(x)∪N(y)|:x,y∈V(G),d(x,y)=2},1989年Faudree等证明了:若3连通n阶图G,NC≥(2n 1)/3,则G是哈密尔顿连通图。据此进一步研究NC2≥(2n 1)/3,而且研究到2连通图,得到下面结果:若2连通n阶图G,NC2≥(2n 1)/3,则G是哈密尔顿连通图或G=ψ。 相似文献
11.
图被称为K1,n-free图,如果它不含有导出子图K1,n。设G是一个具有顶点集V(G)的图,并设g和f是两个定义在V(G)的函数,使得g(x) f(x)对所有V(G)中的点x都成立。设a=max{g(x)|x∈V(G)},b=min{f(x)|x∈V(G)},并有b,a 2,n b/(a-1) 1(如果存在点v∈V(G)使得f(v)≡1(mod2),假定b n-1)。证明了:每个连通的使得∑x∈V(G)f(x)为偶数的K1,n-free图G有(g,f)-因子,如果它的最小度至少是(n-1)(a 1)b 1「b a(n-1)2(n-1) -n-1b「b a(n-1)2(n-1) 2 n-3.这个结果是K.Ota和T.Tokuda(J.GraphTheory.1996,22:59-64.)关于在K1,n-free图中存在正则因子度条件的推广。 相似文献
12.
周思中 《安徽大学学报(自然科学版)》2006,30(5):10-12
设G是一个图,g和f是定义在图G的顶点集上的两个整数值函数,且g≤f.图G的一个(g,f)-因子是G的一个支撑子图F,使得对每个x∈V(F),有g(x)≤dF(x)≤f(x).若图G的边集能划分为若干个边不相交的(g,f)-因子,则称图G是(g,f)-可因子化的.本文研究了图的(g,f)-可因子化的问题,给出了一个图G是(g,f)-可因子化的若干充分条件. 相似文献
13.
设G是一个图,用V(G)和E(G)表示顶点集和边集,并设g和f是定义在V(G)上的两个非负整数值函数且g〈f。图G的一个(g,f)-因子是G的一个支撑子图F使对任意的x∈V(G)有g(x)≤dF(x)≤f(x)。如果过图G的任何三条边不属于它的一个(g,f)-因子,则称图G是一个(g,f)-3-消去图,本文给出了一个图是(g,f)-3-消去图的一个充分条件。 相似文献
14.
15.
设图G的顶点集为V(G),边集为E(G),g和f是定义在V(G)上的2个整值函数,满足对于一切x∈V(G),g(x)≤f(x).若G是一个(mg+rn,mf-rn)-图,1≤n<m,r≥2,且对于x∈V(G),有g(x)≥k≥1,则存在G的一个子图G′,使得G′具有一个(f,g)-因子(n,r)-正交于G的任意给定子图H,其中|E(H)|=nk. 相似文献
16.
设G=(X,Y,E)是二分图,g,f是定义在V(G)上的正整数值函数,且对任意的x∈V(G)有g(x)<f(x).令G是(mg,mf-1)-图,证明了:①若,g(x)≥1,H是G的任一含有m条边的子图.则G有一个(g,,)-因子分解与H-正交.②若g(x)≥2,H是G的任一含有2m条边的子图,则G有一个(g,f)-因子分解与H2-正交. 相似文献
17.
李建湘 《邵阳学院学报(自然科学版)》2001,14(2):91-94
设g和f分别是定义在图G的顶点集合V(G)上的整数值函数,且对每个x∈V(G)有k-1≤g(x)<f(x).给出了(mg+m-1,mf-m+1)-图是随机(m,k)-正交的(g,f)-可因子化图的一个充分条件. 相似文献
18.
设G是一个图,用V(G)和E(G)表示顶点集和边集,并设g和f是定义在V(G)上的两个非负整数值函数且g〈f。图G的一个(g,f)-因子是G的一个支撑子图F使对任意的x∈V(G)有g(x)≤dF(x)≤f(x)。如果过图G的任何三条边都有一个(g,f)-因子,则称图G是一个(g,f)-3-覆盖图,本文给出了一个图是(g,f)-3-覆盖图的一个充分条件。 相似文献