关于图的距离控制数的上界(英文)

对于任意的正整数l,连通图G的顶点子集D被称为距离l 控制集 ,是指对于任意顶点v D ,D中至少含有一个顶点u ,使得距离dG(u ,v) ≤l.图G距离l 控制数γl(G)是指G中所有距离l 控制集的基数的最小者 .确定图G的距离l 控制数γl(G)是NP 问题 .给出了当G是阶数为p (p ≥l + 1 )的连通图时 ,对于任意的正整数l,都有最优上界γl(G)≤ p-Δ+l - 1 l .而且针对某些Δ和l。

具有完美匹配和奇长直径的一类树的RCW数(英文)

连通图G的RCW数定义为RCW(G)=Σu,v V(G)1d+1 d(u,v|G),其中V(G)是图的点集,d(u,v|G)是点u与v之间的距离,d是图G的直径.首先定义了具有完美匹配和奇长直径的一类树,进而确定了这类树的最小,第二小,以及第三小RCW数.

关于超立方体网络的(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.