特殊平面图的全染色

给定一个图G,G的全k染色是指至多用k种颜色,对G的顶点和边同时进行染色,使得相邻的或相关联的两个元素(点和边)不染同一种颜色.图G的全染色数xT(G)是指使G全k染色的最小整数k.Δ(G)是G的最大度,本文对不含从4到k的圈,且3-圈不重点的平面图得出的结论有:如果(Δ,k)分别是(6,4),(5,5),(4,11),则G的全染色数是Δ 1.     

围长为4的没有某些圈的平面图的3-可选择性

对于图G=(V,E),给G的每一顶点v一个颜色列表L(v),G称为L-可选择的,如果存在G的一个着色f,使得对于任意的uv∈E,都有f(u)≠f(v),而且f(v)∈L(v),对于任意的v∈V(G);G称为k-可选择的,如果G为L-可选择的对于任意的满足L(v)=k的L.本文我们证明围长为4的没有8-,9-和13-圈的平面图是3-可选择的.     

推广的Petersen图的相邻顶点可区分的全染色

图的全染色概念是点染色和边染色的推广,图的所有元素(顶点和边)都将染色且任相邻或关联的元素染色不同.邻点可区分的全染色是在正常全染色的定义上,使得相邻顶点的色集不同.本文给出了推广的Petersen图的相邻顶点可区分的全染色.     

笛卡尔乘积图的k-路点覆盖

对于一个图G和一个正整数k,若图G中任意一条阶数为k的路都至少包含集合S?V(G)中的一个顶点,那么集合S就为图G的一个k-路点覆盖。最小的k-路点覆盖基数记为ψ_k(G),为图G的k-路点覆盖数。研究圈图分别与圈图、完全图及完全二部图做笛卡尔乘积图的k-路点覆盖,得到ψ_k(G)相关的精确值和上下界。     

论无标度网的增长和择优

增长和择优机制是无标度网络中两种重要的演化机制,已发现比较重要的择优机制有度择优和秩次择优,比较重要的增长方式有星形图增长和完全图增长.该文首先分析了秩次择优机制对网络度指数的影响,指出可以利用秩次择优来构造度指数在较大范围内变化的模型. 接下来分析了星形图增长和完全图增长的优缺点,并提出了更符合实际情况的模体增长方式,然后结合秩次择优机制和模体增长方式提出了一个新模型——模体增长秩次择优模型,该模型除了具有较宽的度指数范围外,还在度指数大于2.5时具有独立于网络规模的群集系数.     

具有最小连通点对图的C-超图的染色讨论

主要讨论C-超图的染色与点的点对图的连通性之间的关系,证明了对任意给定的不小于3的正整数n,都存在上色数为n且具有最小连通点对图的3一致C-超图.     

点关联较少3-面的平面图的全染色

证明了对每点至多关联2个3-面的平面图,全染色猜想成立. 对每点至多关联2个3-面且Δ(G)≥8的平面图,有x_T(G)=Δ(G)+1.对每点至多关联[Δ(G)/2」个3-面且Δ(G)≥9的平面图,有x_T(G)=Δ(G)+1.     

外平面图度有限制的k-荫度

令ak(G)表示最大度不超过k且能覆盖图G所有边的森林的最小数目.则对于任意的外平面图,当2≤k＜Δ(G)时有ak(G)=「Δ(G)/k.     

拟无爪图的性质

讨论了比无爪图更广泛的图——拟无爪图,得到了以下两个结果： (ⅰ)　若图G是拟无爪图,且满足ω(G-S)≤t(G), 则2t(G)=κ(G). (ⅱ) 若图G是拟无爪图,对于任意的控制集D及任意t∈D,至多存在3点u1,u2,u3∈(V-D)满足N(ui)∩D={t}(i=1,2,3), 则γ(G)=i(G),该结果是最好可能的. 以上结果扩展了无爪图的相应结果.     

一种多层次语义视频对象分割算法

提出一种基于高斯马尔可夫随机场及规则化图划分的多层次语义视频对象分割算法,其主要特点是将视频序列帧中对象的分割看成是“内容树”结构中复合结点的形成过程.首先使用高斯-马尔可夫模型来进行视频帧内的最优标记场标定,然后引入规则化图划分准则进行过分割区域的合并,得到具有语义意义的视频对象.实验表明,本分割算法具有较高的准确性,误差的均值为11.375%,标准方差为0.94%.