广义分数可扩图

研究一类广义分数可扩图即分数(n,k,d)-图的性质.图G是分数(n,k,d)-图即删去G的任意n个顶点后的剩余子图G′含有k-对集,且G′的任意k-对集都可扩充成G′的分数亏格-d对集.得到了分数(n,k,d)-图分别添加边和顶点的一系列递推关系.     

(d,r,k)-析取矩阵的卡氏积

(d,r,κ)-析取矩阵是分组测试理论中的一个Inhibitor模型.利用两个已知的(d,r,k)-析取矩阵定义了它们的卡氏积,并计算了这个新(d,r,κ)-析取矩阵的参数.     

两类图的(d,1)-全标号

主要讨论了W_n与C_m的笛卡尔积和均衡完全r-部图K_r(n)的(d,1)-全标号,并得出了(d,1)-全数λ_d~T(W_n□C_m)和λ_d~T(K_(r(n)))的确切值.     

二元(p,r,d)-码的构作及其应用

令n是一个正整数,[n]={1,2,…,n}.利用集合[叫上的s-子集族((ns))构作了二元(p,r,d)-叠加码,研究了它的容错和析取性质并介绍了它在非适应性群测(Nonadaptive Group Testing)方面的应用.     

一类（k＋1）-色有向图的本原指数

本文定义了一类具有(k+1)-色(k+1)-圈的有向图D(A),得到了它本原的充要条件,并给出了它的本原指数.     

由轮图导出的某些平面图类的星色数

图的星色数是通常色数概念的推广.本文求出了几类由轮图导出的平面图的星色数.前两类是由3-或5-轮图经细分等构造出的,其星色数分别为2+2/(2n+1),2+3/(3n+1)和2+3/(3n-1).第三类平面图是由n-轮图经过Hajos构造得到的,其星色数为3+1/n.本类图的星色数结果推广了已有结论.     

一个关于图是分数(k,n)-临界的邻域并条件

设G是一个图,以及k是满足1≤k的整数.一个图G在删除任意n个顶点后的子图均含有分数k-因子,则称G是一个分数(k,n)-临界图.给出了图是一个分数(k,n)-临界图的一个邻域并条件,并且该条件是最佳的.     

关于可嵌人曲面图的列表(d,1)-全标号问题

图的(d,1)-全标号问题最初是由Havet等人提出的.在本文中,我们考虑了可嵌入曲面图的列表(d,1)-全标号问题,并证明了其列表(d,1)-全标号数不超过△(G)+2d.     

关于(ξ,k)-临界图

设 G为连通图 ,且ξ(G) =k≥ 1 ,若对 G中任意边 e,均有ξ(G\e) =k - 1 ,则称 G为 (ξ,k) -临界图 .本文刻划了ξ- 1 -临界图的若干性质 ,给出了一个图为ξ- 1 -临界图的一些充分或必要条件 ,以及一些ξ- 1 -临界图类 .     

一类裂变图的L(0,1,2 d,d,1)-标号数上界

将图的标号问题由每个顶点需要一个标号的情况推广到每个顶点需要多个标号的情况,给出裂变图的概念以及赋权图的L(0,1,2 d,d,1)-标号的概念,给出R-单位球图对应裂变图的L(0,1,2 d,d,1)-标号数的一个上界.     

On (k,d)-colorings and fractional nowhere-zero flows

The concepts of (k, d)-coloring and the star chromatic number, studied by Vince, by Bondy and Hell, and by Zhu are shown to reflect the cographic instance of a wider concept, that of fractional nowhere-zero flows in regular matroids. © 1998 John Wiley & Sons, Inc. J. Graph Theory 28: 155–161, 1998     

超立方体网络的(d,k)控制数

(d,k)控制数是刻画容错网络中资源共亨可靠性的一个新参数.本文考虑了k维超立方体Qk的(d,k)控制数,得到:γ1,k(Qk)=2k-1(k>1);d=[k/2] 1(k>2)时,γd,k(Qk)=2;d≤[k/2](k≥4)时,3≤γd,k(Qk)≤2k-d 1;以及若d为正整数,且[k/d]=[k/(d-1)] 1,则γd,k(Qk)=γd,k(Qk),其中[k/d].d 1≤k1≤k.     

极大外平面图（r,k）——扇的4染色

定义了一类极大外平面图：(r,k）--扇。证明了当G是以r个顶点的圈Qr为标定界环的(r,k）一扇,G'是以Qr为标定界环的任意极大外平面图时,G和G'有公共四染色;同时对△(G)=r-3的极大外平在图也得到相同的结论。从而证明了四色定理的等价命题在给定条件下成立。     

(a,b,k)-临界图(英)

设G是一个图且设a，b是非负整数，a＜b．如果消去G的任意K个顶点剩下的图有[a，b]-因子，则称图G是（a，b，k）-临界图，本文给出了一个图是（a，b，k）-临界图的一个充分必要条件，讨论了该条件的一些应用，研究了（a，b，k）-临界图的性质。     

A Minimal-Automaton-Based Algorithm for the Reliability of Con(d,k, n) Systems

A d-within-consecutive-k-out-of-n system, abbreviated as Con(d, k, n), is a linear system of n components in a line which fails if and only if there exists a set of k consecutive components containing at least d failed ones. So far the fastest algorithm to compute the reliability of Con(d, k, n) is Hwang and Wright's algorithm published in 1997, where . In this paper we use automata theory to reduce to . For d small or close to k, we have reduced from exponentially many (in k) to polynomially many. The computational complexity of our final algorithm is , where .     

n≤12阶(k,l)-正则极大平面图

我们知道当图的顶点数n>12时不存在正则极大平面图.相关文献提出了(k,l)-正则极大平面图的概念,并讨论了(5,6)-正则极大平面图的存在性.在相关文献中,作者分别讨论了阶n>12的(k,l)-正则极大平面图的存在条件及构造方法.本文讨论了阶n(≤12)的(k,l)-正则极大平面图的存在性,除两种情况外,本文给出了阶n(≤12)的(k,l)-正则极大平面图的存在条件及其一种构造的例子.     

关于超立方体网络的(d,k)独立数

(d,k)独立数是分析互连网络性能的一个重要参数.对于任意给定的图G和正整数d和k,确定G的(d,k)独立数问题是一个NPC问题.因此,确定一些特殊图的(d,k)独立数显得很重要.本文确定了k维超立方体网络的(d,k)独立数等于2,如果d=k≥4或者d=k-1≥6 以及αd,k-t(Qk)=αd,k(Qk),其中0≤t≤k-2,1≤d≤k-t-1.     

有向图的L(j,k)数的上界

给定正整数j≥k,有向图D的一个L(j,k)-标号是指从V(D)到非负整数集的一个函数f,使得当x在D中邻接到y时|f(x)-f(y)|≥j,当x在D中到y距离为二时|f(x)-f(y)|≥k.f的像元素称为标号.L(j,k)一标号问题就是确定(?)j,k-数(?)j,k(D),这个参数等于(?) max{f(x)|x∈V(D)},这里f取遍D的所有L(j,k)-标号.本文根据有向图的有向着色数及最长有向路的长度来研究(?)j,k-数,证明了:(1)对任何有向着色数为(?)(D)的有向图D,(?)j,k(D)≤((?)(D)-1)j;(2)对任何最长有向路的长度为l的有向图D,如果不含有向圈或者D中最长有向圈长度为l 1,则(?)j,k(D)≤lj.并且这两个界都是可达的.最后我们对l=3的有向图给出了3j-L(j,k)-labelling的一个有效算法.     

AT-free图的配对控制集算法

本文给出了配对控制集在AT-free图的BFS-树上分布的结构性质．利用这些性质，我们给出了求解AT-free图类最小配对控制集的多项式时间算法．