排序方式: 共有11条查询结果,搜索用时 15 毫秒
1.
某些整数距离图的染色 总被引:1,自引:0,他引:1
整数距离图是这样一类图G(Z,D),其中,V(G)=Z,两点u,v之间存在一条边,当且仅当|u-v|∈D,这里D是由自然数组成的一个集合.利用组合数学中的一个相关定理和距离图染色中我们已知的一些结论,通过几种周期染色组合的方法,本确定了|D|=4且D中包含{2,3}和|D|=5且包含{2,3,5}时某些距离图G(Z,D)的点色数x(D). 相似文献
2.
Fan 型条件与泛连通性 总被引:2,自引:0,他引:2
设G是n(≥5)个顶点的简单图.本文证明了若对G的任意一对距离为2的顶点u,v都有max{d(u),d(v)}≥(n+1)/2成立,则G中任一对顶点x和y之间存在长为6到n-1的路.,Let G be a simple graph with n(≥5) vertices. In this paper, we prove that if G is 3-connected and satisfies that d(u,v)=2 implies max {d(u),d(v)}≥(n+1) /2 for every pair of vertices u and v in G, then for any two vertices x, y of G, there are (x,y)-paths of length from 6 to n-1 in G, and there are (x,y)-paths of length from 5 to n-1 in G unless G[(N)(x)]=G[(N)(y)]≌K4or K5, or G[(N)(x)],G[(N)(y)]are complete and (N)(x)(n)(N)(y)=φ. 相似文献
3.
4.
L(d,1)-标号着色是L(2,1)-标号着色的推广,这一图的点着色问题来自于无线电波中的频道分配问题,要求图中相邻顶点所着的颜色相差至少d,距离为2的顶点所着颜色必须不相同,由于d:0,1,2时regular tilings的L(d,1)-标号着色数已由Calamoneri和Petreschi给出,本文研究d≥3时所有3种regular tilings的L(d,1)-标号着色,给出它们的L(d,1)-标号着色数,结合Calamoneri和Petreschi的结果,对所有非负整数d,regular tilings的L(d,1)-标号着色数已完全确定。 相似文献
5.
圆色数和分式色数是图的点色数的 2个推广 .当图的圆色数等于分式色数时 ,称此图是starextremal.本文研究了生成集为 {± 1,±k}具有starextremal特征的循环图 相似文献
6.
图的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)边跨度. 相似文献
7.
对于给定图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-部完全图、正三角形网格、 正四边形网格以及弦图等图类的边跨度,并给出了确切的数值. 相似文献
8.
NEWSUFFICIENTCONDITIONFORHAMILTONIHNPROPERTIESINGRAPHSSongZengmin(宋增民)(DepartmentofMathematicsandMechanics)NEWSUFFICIENTCONDI... 相似文献
9.
ANOTEONPANCYCLICORIENTEDGRAPHSongZengmin(宋增民)ChenLiming(陈黎明)(DepartmentofMathematicsandMechanics)ANOTEONPANCYCLICORIENTEDGRAP... 相似文献
10.