一类特殊de Bruijn有向图的谱

分析了一类特殊deBruijn有向图 B(2 ,n)的结构 ,获得了B(2 ,n)的谱 .B(2 ,n)的特征值为 0与 2 ,且它们所对应的重数分别为 2 n 1与 1.

广义de Bruijn有向图和Kautz有向图的限制性弧连通度

有向图的限制性弧连接度是测量互连网络容错性的重要参数.本文证明了对于直径k≥4和参数d≥4的广义de Bruijn有向图BG(n, d),它的限制性弧连通度是2d-2.对于直径k≥4和参数d≥4或者d≥3, k≥5, n和d的最大公约数g.c.d(n,d)≥2和n可以被d+1整除的广义Kautz有向图KG(n, d),它的限制性弧连通度为2d-2.作为结论, BG(n, d)和KG(n, d)的超限制性弧连通性可以直接得出.本文还证明了对于任意的强连通有向图D有λh(D)≤min{ξh(D),|V1|λ(D2),|V2|λ(D1)}.另外,对于直径k≥4,证明这两类有向图分别跟自己做笛卡尔积得到的有向图的限制性弧连通度分别是d≥3,λ2(BG(n, d)×BG(n, d))=4d-2;d≥2,λ2(KG(n, d)×KG(n, d))=4d-2.

广义de Bruijn有向图的k-元控制集

G=(V,A)表示一个有向图,其中V和A分别表示有向图G的点集和弧集。对集合Dk■V(G),如果对于任意点v∈V(G),都存在k个点ui,1≤i≤k(可能存在某个ui和v是同一点)使得(ui,v)∈A(G),则称Dk是G的一个k-元控制集。有向图G的k-元控制数γ×k(G)是G的最小k-元控制集所含点的数目。给出了广义de Bruijn有向图的k-元控制数的新上界,并且具体给出了构造广义de Bruijn有向图的k-元控制集的方法。此外,对某些特殊的广义de Bruijn有向图,通过构造其k-元控制集,进一步改进了它们k-元控制数的上界。

广义de Bruijn和Kautz有向图的距离控制数(英文)

对于任意的正整数(?),强连通图G的顶点子集D被称为距离(?)-控制集,是指对于任意顶点v(?)D,D中至少含有一个顶点u,使得距离dG(u,v)≤(?)．图G距离(?)- 控制数γe(G)是指G中所有距离(?)-控制集的基数的最小者．本文给出了广义de Bruijn 和广义Kautz有向图的距离(?)-控制数的上界和下界,并且给出当它们的距离2-控制数达到下界时的一个充分条件．从而得到对于de Bruijn有向图B(d,k)的距离2-控制数γ2(B(d,k))= ．在该文结尾,我们猜想Kautz有向图K(d,k)的距离2-控制数γ2(K(d,k))= .

广义de Bruijn和Kautz有向图的双向控制集

设G=（V,A）是一个有向图,其中V和A分别表示有向图G的点集和弧集.对集合TV（G）,如果对于任意点v∈V（G）／T,都存在点u,w∈T（u,w可能是同一点）使得（u,v）,（v,w）∈A（G）,则称T是G的一个双向控制集.有向图G的双向控制数γ-＊（G）是G的最小双向控制集所含点的数目.提出了广义de Bruijn和Kautz有向图的双向控制数的新上界,改进了以前文献中提出的相关结论.此外,对某些特殊的广义de Bruijn和Kautz有向图,通过构造其双向控制集,进一步改进了它们双向控制数的上、下界.

关于de Bruijn图中限长路的注记(英文)

Imase等人证明了 :对于deBruijn有向图B(d ,k)中任何两个不同的顶点x和y ,存在d- 1条内点不交且长度都不超过k+ 1的 (x ,y)路 .但证明很长而且包含许多令人厌烦的验证 .

有向图语言

经典形式语言有两条主线,就是自动机线索与形式文法线索。利用有向图理论和有向图半群理论建立了另一条线索——有向图语言,讨论了两类特殊的有向图语言——de Bruijn有向图语言和Kautz有向图语言,引入了连通语言及语言的直径等概念,计算出了deBruijn有向图语言和Kautz有向图语言的直径。

广义二元有向De Bruijn图的限制弧连通度

限制弧割是将有向连通图G分割成阶数至少为2的双向连通分支的弧割,有向图G的最小限制弧割的弧数称为图G的限制弧连通度.易见,一个有向图(2,)G B n至少有4个顶点才有限制弧割.本文证明了:当n³7时,二元有向图De Bruijn图是极大限制弧连通的.

一些DNA图的标号

为了读取DNA序列,Blazewicz等人提出了(α,k)-可标号的有向图的概念,称有向图D是DNA图若D是(4,k)-可标号的.基于此,证明了(α,k)-可标号的有向路和有向圈的充要条件.设T是一棵只有一个入(出)度为0的点的定向树,还证明了T是(α,k)-可标号的有向图的必要条件和T是DNA图的充要条件.