几类轮图构造图的(2,1)-全标号

研究了与频道分配有关的一种染色问题——(p,1)-全标号。(p,1)-全标号是从V(G)∪E(G)到集合{0,1,…,k}的一个映射,满足:G的任两个相邻的顶点得到不同的整数;G的任两个相邻的边得到不同的整数;任一个点和与它相关联的边得到的整数至少相差p。称最小的数k为图G的(p,1)-全标号数。根据所构造图的特征,利用穷染法,得到了这些图的(2,1)-全标号数。     

几类联图的(2,1)-全标号

研究了与频道分配有关的一种染色问题——(p,1)-全标号。图G的(p,1)-全标号是一个映射f:V(G)∪E(G)→{0,1,…,k},使得:G的任两个相邻的顶点得到不同的整数;G的任两个相邻的边得到不同的整数;任一个点和与它相关联的边得到的整数至少相差p。(p,1)-全标号的跨度是指两个标号差的最大值。图G的(p,1)-全标号的最小跨度叫(p,1)-全标号数,记作λTp(G)。根据联图的特征,利用穷染法,得到了几类联图的(2,1)-全标号数。     

关于图的(d,1)-全标号

给出了星图、树图和均衡完全三部图的(d,1)-全数。     

路与扇形图联图的(2,1)-全标号

图G的一个k-(2,1)-全标号是一个映射f:V(G)∪E(G)→{0,1,2,…,k},使得(1)相邻的顶点标不同的号,(2)相邻的边标不同的号,(3)顶点与所关联的边标号数相差至少为2.图G的(2,1)-全标号数定义为G有一个k-(2,1)-全标号的最小的k值,记为λT2(G).根据路与扇图联图的特点,找到一种特殊的标号方法,给出路与简单扇图联图的(2,1)-全标号数的上界.     

路与简单扇图联图的(2,1)-全标号

图G的一个k-(2,1)-全标号是一个映射f:V(G)∪E(G)→{0,1,2,…,k},使得(1)相邻的顶点标不同的号,(2)相邻的边标不同的号,(3)顶点与所关联的边标号数相差至少为2.图G的(2,1)-全标号数定义为G有一个k-(2,1)-全标号的最小的k值,记为λT2(G).根据路与扇图联图的特点,找到一种特殊的标号方法,给出路与简单扇图联图的(2,1)-全标号数的上界.     

两类特殊的图Cm·G的（p，1）-全标号

设G为任意简单图，v∈V（G），把G拷贝m次，然后把拷贝后的m个v连成圈，所得到的新图记为Cm·G（v）．本文给出了两类特殊的图Cm·G的（p，1）-全标号．     

若干圈的广义冠图的(2,1)-全标号(英文)

研究了与频率分配有关的一种染色问题:(2,1)-全标号,它是对图的全染色的一种推广,根据圈的广义冠图的构造特征,利用穷染法,给出了一种标号方法,得到了几类圈的广义冠图的(2,1)-全标号数.     

一类二部图的(d,1)-全标号

图G的一个k-(d,1)-全标号是一个映射f:V(G)∪E(G)→｛0,1,2…,k｝,使得(1) 相邻的顶点标不同的号;(2) 相邻的边标不同的号;(3) 顶点与所关联的边标号数相差至少为d (d≥2)。图G的(d,1)-全标号数定义为G有一个k-(d,1)-全标号的最小的k值。给出了一类二部图的(d,1)-全标号数。     

图的（3，1）- 全标号

图G的(p,1)-全标号是对G的点和边进行标号,满足:任意两个相邻的点得到不同的标号,任意两个相邻的边得到的标号也不同.并且任意一个点与和它相关联的边所得到的标号的差的绝对值至少为p,其中在全标号中最大的标号与最小的标号的差值称为全标号的跨度,记一个(p,1)-全标号中最小的跨度为λTp.证明了当p=3,Δ(G)≥9时,λT3≤2Δ(G)+1.     

立方圈的(d,1)-全标号

一个图G的(d,1)-全标号是V(G)∪E(G)到整数集合的一个映射f,使得|f(x)-f(y)|≥{1,若顶点x和y相邻,1,若边x和y相邻,d,若顶点x和边y相关联。主要研究了立方圈C_l~3的(d,1)-全标号,得到了d限制条件下立方圈C_l~3的(d,1)-全数的确切值。     

两类全图的（2,1）-全标号

一个图G的(p,1)-全标号是一个映射f∶V(G)∪E(G)→{0,1,…k},使得:G的任两个相邻的顶点得到不同的整数;G的任两个相邻的边得到不同的整数;任一个点和与它相关联的边得到的整数至少相差p.(p,1)-全标号的跨度是指两个标号差的最大值.图G的(p,1)-全标号的最小跨度叫(p,1)-全标号数,记作λpT(G).得到了两类全图的(2,1)-全标号数.     

几类圈构造图的(p,1)-全标号

一个图G的（p,1）-全标号是一个映射f：V（G）∪E（G）→{0,1,…k},使得：G的任两个相邻的顶点得到不同的整数;G的任两个相邻的边得到不同的整数;一个点和它的邻边得到的整数至少相差p．（p,1）-全标号的跨度是指两个标号差的最大值．图G的（p,1）一全标号的最小跨度叫（p,1）-全标号数,记作λP^T（G）．给出了几类圈构造图的（p,1）一全标号．     

图上串行细胞自动机的几个结果(Ⅱ)

讨论了图上串行细胞自动机的两个猜想之间的关系，给出了对给定的π，∑[FY，π]：Aut(Y)成立的必要和充分条件．     

关于几类DNA标号图和DNA图的结果

在分子生物学中,DNA链的杂交测序的计算和重构阶段可用DNA图作为数学模型,因此,DNA图得到广泛的研究^[1.2]．为了读取DNA序列,Blazewicz等人提出了可（α,k）-标号有向图的概念,并称有向图D是DNA图,如果D是可（4,k）-标号的．2008年,原军等证明了可（α,k）-标号的有向路和有向圈的充要条件．本文证明了有向路和有向圈可（α,k）-标号的一个性质,并利用有向线图的理论证明了本文所指的伪二部单向完全图D0（A,B）、k部广义路P（V0,V1,…,VK-1）、k部广义圈C（V0,V1,…,Vk-1）以及k部广义树T（V0,V1,…,Vk-1）均是DNA标号图．进而给出并证明了二部单向完全图D（V1,V2）和k部广义路P（V0,V1,…,Vk-1）为DNA图的充要条件．     

关于几乎k-可扩图的若干结论

设G是具有奇数个顶点的图,k是非负整数且满足V(G)≥2k+1,若G中任意一个k-匹配都可以扩充为G的一个几乎完美匹配,则称G是几乎k-可扩图.文中证明了连通的几乎1-可扩图与2-连通的几乎k-可扩二部图分别添加一个新边后仍保持原来的可扩性.     

自补图的L(2,1)-标号

研究自补图G的L（2,1）-标号问题,证明了自补图的L（2,1）-标号数满足λ（G）≤2△。验证了关于一般图的L（2,1）-标号数的猜想λ（G）≤△2对于自补图的正确性。