关于循环有向图的强连通度

本文定义的循环有向图D(n;S)在分布式环形计算机互连网络设计中被广泛运用。本文证明了D(n;S)的强连通度k>2/3|S|。     

有向图超级弧连通的充分条件

如果有向图D的任一最小弧割都是发向某个度为δ的顶点的弧集或者是由某个度为δ的顶点发出的弧集,则称有向图D是超级弧连通的,给出了有向图超级弧连通的一些充分条件.     

局部连通度至多是1的有向图的最大弧数

设 D=(V,A)是局部连通度至多是1的严格有向图,令 n 和 e(D)分别表示 D 的点数和弧数.本文证明:若 n≤7,则 e(D)≤2(n-1);若 n≥7,则 e(D)≤[(n~2)/4];并且给出极图的完全刻画.     

强哈密尔顿连通有向图的一个注记

利用收缩技术,证明了1)阶为n=2k且最小半度至少是k的有向图D是强哈密尔顿连通的,除非D属于某些图类;2)2强连通且包含n个顶点、(n-1)(n-2)+4条弧的有向图是强哈密尔顿连通的,除非D属于某些图类.     

有向图的拟强连通和超拟强连通性

Geller,F.和Harary,F.在文献[2]中对有向图的强连通,单侧连通和弱连通给出了几个性质定理。Berge,C.在[3]中曾定义了有向图的拟强连通。并对拟强连通与有向树的关系等给出了两个定理。本文对有向图的拟强连通和超拟强连通性得到了与[2]中相应的结果。     

依赖团数的有向图极大弧连通的充分条件

互连网络通常以有向图为模型,有向图的弧连通度是网络可靠性的一个重要参数.设D是一个有向图,δ(D)是最小度,弧连通度为λ(D),则λ(D)≤δ(D).当λ(D)=δ(D)时,称有向图D是极大弧连通的.本文给出了依赖团数的有向图极大弧连通的一些充分条件.     

循环图的连通度

设Ｇ＝Ｇｎ（ｉ１,ｉ２,…,ｉｒ）是连通循环图,且ｘ（Ｇ）〈δ（Ｇ）,本文得到了其连通度的明确表达式：ｘ（Ｇ）＝ｍｉｎ（ｍ／Ｍ（ｎ／ｍ,Ｋ）／：ｍ是ｎ的真因子,且／Ｍ（ｎ／ｍ,Ｋ）／〈ｎ／ｍ－１）。     

极小强连通本原有向图的本原指数集

本文的主要结果为:(1)当一个n阶极小强连通本原有向图至少含三个不同圈长时,有γ(D)≤[1/2(n~2-6n+14)](当n≥14时)。(2)e(n)≥[1/2(n~2-6n+16)],即从6到[1/2(n~2-6n+14)]的所有正整数都是某个n阶极小强连通本原有向图的本原指数。(3)给出了n阶极小强连通本原有向图的本原指数集NE_n的明确表达式。     

本原极小强连通有向图1—指数的下界

本文给出了n阶本原极小强连通有向图1-指数的下图:expD(1)4.且这个下界是可以达到的.     

强连通双圈有向图的无符号拉普拉斯谱刻画

设$\overrightarrow{G}$ 是一个强连通双圈有向图, $A(\overrightarrow{G})$是其邻接矩阵.设$D(\overrightarrow{G})$ 是$\overrightarrow{G}$的顶点出度的对角矩阵, $Q(\overrightarrow{G})=D(\overrightarrow{G})+A(\overrightarrow{G})$是$\overrightarrow{G}$ 的无符号拉普拉斯矩阵. $Q(\overrightarrow{G})$的谱半径称为$\overrightarrow{G}$的无符号拉普拉斯谱半径.在这篇文章中, 确定了在所有强连通双圈有向图中达到最大或最小无符号拉普拉斯谱半径的唯一有向图. 此外,还证明了任意一个强连通双圈有向图是由它的无符号拉普拉斯谱所确定的.     

n阶本原极小强连通有向图k-指数的最小值

本文证明了:当1≤k≤︱n/4︱时,n阶本原极小强连通有向图k指数的最小值是4。     

关于有向图的强符号可解性

Hansen已提出一个判别强符号可解有向图的一般算法,其时间复杂性为O(mn).仔细分析算法,尚存在很多重复过程而耗费时间。从图论的观点看,最有效的算法应当是O(m)。本文进一步研究强符号可解有向图的一些基本性质,在此基础上发现这类图存在一种嵌套结构。结合有向图的DFS纵深搜索法,我们找到一个最有效的递推算法,其时间复杂性恰为O(m)。从而,使符号有向图的判别问题满意地获得解决。     

有向循环图强连通度的下界

为简便计,本文采用文[1]中的定义和符号,而未说明的概念或符号引自[3].本文仅讨论有限、简单有向图. 有向图D=(V,A)称为强连通的,如果对D的任两顶点u与v,在D中同时存在(u,v)—有向路和(v,u)—有向路,C(?)V称为D的点割集,如果D—C非强连通或是单点.D的所含点数最少的点割集称为最小点割集,其阶数定义为D的强连通度,记为k(D)或k. 循环有向图D(n,S)定义如下:     

随机有向循环图的连通度

In this paper, we prove that almost all circulant digraphs are strongly connected. Furthermore, for any given positive integer m, we show that almost every circulant digraph C has connectivity at least m/1 m(d(C) 1), where d(C) is the vertex degree of C.     

关于代数连通度的一个注记

图G=(V,E)的次小的拉普拉斯特征值称为G的代数连通度,记为α(G).设δ(G)为G的最小度.Fiedler早在1973年便证明了α(G)≤δ(G),但他未能给出等号成立的极图刻划.后来,我们在[6]中确定了当δ(G)≤1/2|V(G)|时α(G)=δ(G)的充要条件.本文中,我们将确定任意情况下α(G)=δ(G)成立的所有极图.     

依赖团数的有向图极大与超级边连通的度序列条件

互连网络通常以有向图为模型,有向图的弧连通度是网络可靠性的一个重要参数.给出了依赖团数的有向图极大和超级边连通的度序列条件.     

Bubble-sort网络的连通度和超连通度

Bubble-sort网络Bn是(n-1)-正则,点传递的二部图.在这篇文章中,我们确定了当n≥2时,Bn的(边)-连通度为n-1;当n≥3时,Bn的超(边)-连通度为2n-4.     

围长为2的本原极小强连通有向图的1-指数集

本文研究了围长为2的本原极小强连通有向图的1-指数，证明了：当n为偶数时{4，5，7，8，9，11，…，2n-7，2n-5，2n-4}真包含 En（1）。     

含有两个非临界点的强连通定向图的弧数

证明顶点数为$n\geq 4$,弧数为$m\geq {n-1 \choose 2}+3$的强连通定向
图$D$中存在两点$u^*$、!$v^*$,使得$D-u^*$和$D-v^*$都是强连通的, 并用例子说明这里所给的
关于弧数的下界是紧的.     

4p阶二面体群连通3度Cayley有向图的正规性

设G是一个有限群,S是G的不包含单位元1的非空子集,定义群G关于S的Cayley(有向)图X:=Cay(G,S)如下:V(X)=G,E(X)={(g,sg)|g∈G,s∈S}.Cayley(有向)图X:=Cay(G,S)称为正规的,如果G的右正则表示R(G)在X的自同构群Aut(X)中是正规的.设G是4p阶二面体群(p为素数).考察了Cay(G,S)连通3度的正规性,并给出了这些图的全自同构群.