共查询到17条相似文献，搜索用时 215 毫秒
1.
给定一个图G和2个正整数j和k,图G的一个m-L(j,k)-边标号是从图的边集到非负整数集合{0,1,…,m}的一个映射,该映射满足相邻的边所对应的整数相差至少为j,距离为2的边所对应的整数相差至少为k.在图G的所有m-L(j,k)-边标号中,最小的整数m称为图G的L(j,k)-边标号数,记为λ'j,k(G).项链是一类特殊的Halin图,研究了项链的L(1,2)-边标号,给出了项链的L(1,2)-边标号数的上界和下界,并且此上界和下界都是可达的. 相似文献
2.
对于给定图G顶点集上一个非负整数函数f,满足:若dG(u,v)＝1,f(u)-f(v)≥d;若 dG(u,v)＝2,f(u)-f(v)≥1.称f 为L(2,1)-标号.这是由频道分配问题抽象出来的数学模型.本文主要研究该标号问题的一个参数,即边跨度,记作βd(G)＝minf max{f(u)-f(v):u∈V(G)},即对于所有正常的L(d,1)-标号,使得相邻顶点标号之差的最大值达到最小.本文主要讨论了圈Cn、树T、 k-部完全图、正三角形网格、 正四边形网格以及弦图等图类的边跨度,并给出了确切的数值. 相似文献
3.
图的L(s,t)-标号的概念来自频道分配问题.设s和t是2个非负整数.图G的一个L(s,t)-标号是一个从G的顶点集到整数集的映射,满足:①任意2个相邻顶点对应的整数相差至少为s;②任意2个距离为2的顶点对应的整数相差至少为t.给定图G的一个L(s,t)-标号f,的L(s,t)边跨度定义为max{|f(u)-f(v)|:(u,v)∈E(G)},记为βst(G,f).图G的L(s,t)边跨度定义为min{βst(G,f):f取遍图G的所有L(s,t)-标号},记为βst(G).设T是一棵最大度为△(≥2)的树.证明了:若2s≥t≥0,则βst(T)=([△/2]-1)t s;若0≤2s＜t且△为偶数,则βst(T)=[(△-1)t/2];若0≤2s＜t且△为奇数,则βst(T)=(△-1)t/2 s.同时完全确定了2条路的笛卡儿乘积图和正四边形格图的L(s,t)边跨度. 相似文献
4.
设k和d是2个互素的正整数且k≥2d．G^dk是一个图,它的顶点集合为{0,1,…,k-1},边集合为{ij｜d≤｜i-j｜≤k-d,i,j=0,1,…,k-1}．图G的圆色数χc（G）定义为使得图G与G^dk同态的2个正整数k和d的最小比值k／d．研究了χc（G）和χc（G-v）之间的关系,对任意顶点v求出了χc（G^dk-v）的精确值,给出了具有对任意顶点χc（G-v）=χc（G）-1和其他特定性质的图类;并对图的圆色数的一些下界进行了探讨,给出了图的圆色数达到下界χc-1＋1／d的充要条件,这里χ和α分别是图G的点色数和独立数． 相似文献
5.
王德元 《唐山师范学院学报》1996,(Z1)
1990年,Rosa给出了k公平图的概念。 定义:设简单连通图G=(A,E),有正整数k≥2,若存在映射f:A(G)→[0,k—1],导出映射f~*:E(G)→[0,k—1],使得f~*(uv)=│f(u)—f(v)│,Auv∈E(G),Ai≠j,i、j=0,1,…,k—1,满足 标号为i的点的个数与标号为j的点的个数之差≤1; 标号为i的边的个数与标号为j的边的个数之差≤1.则称f为G的k公平标号,G称为k公平图。其中 相似文献
6.
若图G的顶点可以用一个关于不同整数的标号函数f给出,使得对于G的任意两个不同的顶点u 和v,uv 是G 的边当且仅当f(u) + f(v) =f(w),w为G 的某个顶点,则图G称为整和图(integral sum graph).现给出完全三部图K1,1,r r≥3的(整)和数、完全三部图K1,r,r r≥2(整)和数的一个上下界,并证明了扇图 Fn 及任意个扇图在中心处相交构成的图是整和图,同时得到荷兰风车Dn 也是整和图. 相似文献
7.
高炜 《昆明师范高等专科学校学报》2012,(6):5-9
若删除G中任意一个独立集后得到的图依然是分数（g,f,m）-消去图,则称G为分数ID-（g,f,m）-消去图．将若干个关于分数消去图邻域并条件的结论推广到分数ID-消去图,证明了如下两个结论：1）阶为n的图G满足n≥12k＋6m-11,6（G）≥n/3＋k＋m,且／NG（x）UG（y）/≥2n/3对G中任意一对不相邻的顶点x,y都成立,则G是分数ID-（k,m）-消去图;2）若δ（G）≥（an/2a＋b）＋（b2（i-1）/a＋2m,n〉（（2a＋b）[i（a＋b）＋2m-2]）/a,且/NG（x1）u…uNG（x1）/≥（a＋b）n/2a＋b,对V（G）的所有独立集{x1,……,xi}都成立．则G是分数ID-（g,f,m）-消去图． 相似文献
8.
设f是图G的一个使用了k种色的正常全染色．对G的任意顶点u,用Cf（u）或C（u）表示在f下点u的颜色以及与u关联的所有边的颜色构成的集合,如果对G的任二不同顶点u与v,均有C（u）≠C（v）,那么称,为G的点可区别（正常）全染色．使得G有点可区别正常全染色的最小的k叫做G的点可区别全色数,本文给出Pm∨Pn的点可区别全色数（2≤m〈n）． 相似文献
9.
图G的L(j,k) 标号是图的顶点集到非负整数集的一个映射, 使得相邻顶点所对应的整数相差至少为j,距离为2的顶点所对应的整数相差至少为k. 对于图G的一个L(j,k) 标号f, 定义其L(j,k) 边跨度为βj,k(G,f)=max{f(x)-f(y):{ x,y}∈E(G)}. 图G的L(j,k) 边跨度定义为βj,k(G),它是G的所有L(j,k) 标号f的L(j,k) 边跨度中最小的. 图G的实值L(j,k) 标号是整数L(j,k)标号的推广, 是满足相应的距离一条件和距离二条件的从顶点集到实数集的一个映射. 图G的实值L(j,k)标号的边跨度记为j,k(G). 研究了图的实值L(j,k)边跨度和整数L(j,k)边跨度的若干性质, 完全确定了所有圈以及完全t-部图的边跨度. 相似文献
10.
《钦州师专钦州教院学报》1997,12(2):67-72
设G是连通偶图，（X1，X2）是其顶点的二分类，|X1|=|X2|=n,δ（G）≥t≥3。证明了若任意,u,v∈Xi，蕴含|N(u)∪N（v)|≥n-（t-2），i＝1，2，则当t=8时G是点泛圈偶图。 相似文献
11.
为了得到一个路Pm与一个完全图Kn的直积Pm×Kn的L（2,1）-标号数,通过归纳猜想,分类讨论,证明了m=3或4时,Pm×K3的L（2,1）-标号数为6,m≥5时,Pm×K3的L（2,1）-标号数为7,m≥5且n≥3时,Pm×Kn的L（2,1）-标号数的上界是3n-2. 相似文献
12.
13.
研究了两个均同构于完全二部图Km,n的图G1=(X1,Y1)与G2=(X2,Y2)的匹配和Bm,n的L(2,1)-标号问题,得到了下面的结果:(1)若X1中元素完全与X2中元素相匹配且m,n>3,则Bm,n的L(2,1)-标号数为m+n;(2)若X1中元素不完全与X2中元素相匹配且m,n>6,则Bm,n的L(2,1)-标号数为m+n+1. 相似文献
14.
管训贵 《黄冈师范学院学报》2012,32(6):10-11
对于正实数x,设π（x）表示适合p≤x的素数p的个数.对于正整数k、n,设fk（n）=π（x）＋π（2kx）＋…＋π（nkx）及Sk（n）=1k＋2k＋…＋nk.证明了：当x≥4且n≥[（k＋1）e1.2]时,fk（n）≥π（Sk（n）x）. 相似文献
15.
两个图G1和G2的笛卡尔积图G1×G2定义为如下的图：V（G1×G2）=V（G1）×V（G2）,E（G1×G2）={（u1,u2）（v1,v2）｜u1=v1且u2v2∈E（G2）,或者u2=v2且u1v1∈E（G1）}．图的交叉数是图论中的一个重要拓扑参数,而确定图的交叉数是一个完全胛一问题．本文确定了若干树Tn（n≤4）与圈Cm的笛卡尔积图的交叉数． 相似文献
16.
设d是非平方正整数,u、v是适合u^2-dv^2=1的正整数,a=u＋v√d,证明了n∑k=0[a^k]=（a^n＋1）（a^n-1）/（a-1）a^n-（n-1）,其中[a^k]是a^k的整数部分。 相似文献
17.
研究了两类有向图的正交因子分解问题,得到如下结论：1）设G是（mg＋nk,mf-nk）-有向图,其中1≤n〈m,H是G的任意一个有nk条边的有向子图,其中g≥k≥1.则G中存在子图R,R具有（g,f）-因子分解k-正交于H;2）设G是（0,mf-m＋1）-有向图,则对G中任意给定的有向2m-星K1,2m,G有一个（0,f）-因子分解2-正交于K1,2m. 相似文献