用循环图构造可靠通讯网络

本文得到了５度、７～１５度连通循环图的连通度等于其度数的充要条件。从而可用循环图构造可靠通讯网络。     

连通图的度序列及连通平面图的低度点个数

美国数学家Bondy给出了一个非负整数序列为简单图的度序列的充要条件.本文对此进行了发展,证明了一个正整数序列为连通简单图的度序列的充要条件;然后在此基础上又探讨了平面图的低度点个数问题并定义了描述连通平面图的低度点个数的一个概念φ(n,m),并对某些低阶平面图求出了φ(n,m)的值.最后给出了φ(n,m)的上下界.     

2n-正则简单图的边连通度

图的各种连通度概念被先后用来研究网络可靠性问题.对于0到2n之间的任意一个偶数2m,构造了一个2n-正则简单图,使得其边连通度的值为2m.从而得到:2n-正则简单图的边连通度能够取{0,2,4,…,2n}中的任何一个偶数.     

关于图的连通DOMINATION的若干结果

设G是n阶连通图.γ_c(G),d_c(G),i(G)和ir(G)分别表示G图的连通Domination数,连通Domatic数,独立Domination数和Irredundance数,k(G)表示G的连通度.本文证明了下列结论. (1) 如n≥3,则i(G) γ_c(G)≤n [n/3]-2; (2) γ_c(G)≤4ir(G)-2; (3) γ_c(G)≤k(G) 1; (4) 如G≠K_n,则d_c(G)≤k(G). 此外,本文给出了满足等式γ_c(G) γ_c(G)=n和γ_c(G) γ_c(G)=n 1的图G的一个特征.     

局部(F_4)条件下的两指标Banach空间值鞅的不等式及其在极限定理中的应用

本文中,我们用N~r表示r维正整数格点组成的集合(r≥1,r为整数),N~r中的点用粗写的英文小写字母表示,有时用带下标或不带下标的字母z表示,如n=(n_1,n_2,…,n,)∈N~r, 在N~r中我们定义如下的顺序关系:若n=(n_1,n_2,…,n_r),n'=(n'_1,n'_2,…,n'_r)∈N~r,n≤n'n_i≤n'_i,i=1,2,…,r,若i=(i_1,i_2,…,i_r)j=(j_1,j_2,…,j_r)∈N~r,i相似文献   

太阳图与路的笛卡儿积图的任意可分性（英文）

一个阶为n的图G称为是任意可分的(简作AP),如果对于任一正整数序列τ=(n₁,n₂,…,n_k)满足n=n₁+n₂+…+n_k,总是存在顶点集V(G)的一个划分(V₁,V₂,…,V_k)满足:对于i∈[1,k],|V_i|=n_i,且子图G|V_i|是图G的V_i导出的一个连通子图.我们用S~*=S(n;m₁,m₂,…,m_n)来表示最大度△(S~*)=3的太阳图.本文讨论了图S~*P_m(m≥3)的任意可分性.     

图的上可嵌入性与圈中顶点度

本文利用非上可嵌入图的充要条件,结合圈中顶点最大度与图的上可嵌入性之间的关系,得到了下两个结果:(1)设G是2-边连通简单图,若对G中任意圈G,存在点x∈C满足,d(x)>|V(G)|/3 1,则图G是上可嵌入的,且不等式的下界是不可达的.(2)设G={x,y;E}为简单二都图,且是2-边连通的. |x|=m,|Y|=n(m,n≥3),若对G中任意圈C,存在点x∈C且x∈X满足d(x)>n/3 1,则图G是上可嵌入的,且不等式的下界是不可达的.     

(n,k)-排列图的条件连通度(英文)

点连通度是衡量互联网络容错性的一个重要参数.尽管点连通度能正确地反映了系统的容错性能,但是不能正确反映大规模网络的健壮性能.条件连通度通过对各分支附加一些要求(当整个网络被破坏时)来克服这个缺点.给定一个基于图G的网络和一个正整数l,G的R~l-连通度,记为k~l(G),定义为图G的最小节点子集的节点数,使其去掉后,G是不连通的,且每个分支的最小度至少是l.在本文中,我们得到了(n,k)-排列图的条件连通度k~l(A(_n,k))=[(l+1)k-l](n-k)-l,其中k≥l+2,n≥k+l.     

超级限制边连通二部图的充分条件

设S是连通图G的一个边割.若G-S不包含孤立点,则称S是G的一个限制边割.图G的最小限制边割的边数称为G的限制边连通度,记为λ'(G).如果图G的限制边连通度等于其最小边度,则称图G是最优限制边连通的,简称λ'-最优的.进一步,如果图G的每个最小限制边割恰好分离出图G的一条边,则称图G是超级限制边连通的,简称超级-λ'的.设G是一个最小度δ(G)≥2的n≥4阶二部图,ξ(G)是G的最小边度.本文证明了(a)若ξ(G)≥(n/2-2)(1+1/δ(G)-1),则G是λ'-最优的;(b)若ξ(G)>(n/2-2)(1+1/δ(G)-1),则G是超级-λ'的,除非图G是K2,n-2,n≥6或是Cartesian积图Kn/4,n/4×K2,其中n≥8且n整除4.最后,论文举例说明该结果是最好可能的.     

完全对换网络的限制连通度

完全对换网络是基于 Cayley 图模型的一类重要互连网络. 一个图 G 的 k-限制点(边)连通度是使得 G-F 不连通且每个分支至少有 k 个顶点的最小点(边)子集 F 的基数, 记作 \kappa_{k}(\lambda_{k}). 它是衡量网络可靠性的重要参数之一, 也是图的容错性的一种精化了的度量. 一般地, 网络的 k-限制点(边)连通度越大, 它的连通性就越好. 证明了完全对换网络 CT_{n} 的 2-限制点(边)连通度和 3-限制点(边)连通度, 具体来说: 当 n\geq4 时, \kappa_{2}(CT_{n})=n(n-1)-2, \kappa_{3}(CT_{n})=\frac{3n(n-1)}{2}-6; 当 n\geq3 时, \lambda_{2}(CT_{n})=n(n-1)-2, \lambda_{3}(CT_{n})=\frac{3n(n-1)}{2}-4.     

无限循环图的超边连通性(英文)

本文证明了 ,在一切具有有限跃度序列的无限循环图中 ,只有C( 1 ) ,C( 1 ,2 )和C( 1 ,2 ,3)不是超边连通的 ,而且C( 1 )和C( 1 ,2 )是其中仅有的两个非最大边连通图 .     

若干并图的优美标号

证明了,对任意大于1的自然数m,n,p,非连通图(■ V ■)∪K_(n,p)是优美图;当k≤p,m=kn+3或m=kn+1时,非连通图(P_2 V ■)∪K_(n,p)是优美图;当p≥2,m=3k+1时,非连通图(P_2 V ■)∪K_(3,p)是优美图;对任意正整数n,p,非连通图(P_1 V P_(2n+2))∪_(n,p)是优美图.     

关于三圈图的拉普拉斯谱半径的一些结果

边数等于点数加二的连通图称为三圈图.~设 ~$\Delta(G)$~和~$\mu(G)$~
分别表示图~$G$~的最大度和其拉普拉斯谱半径,设${\mathcal
T}(n)$~表示所有~$n$~阶三圈图的集合,证明了对于~${\mathcal
T}(n)$~的两个图~$H_{1}$~和~$H_{2}$~,~若~$\Delta(H_{1})>
\Delta(H_{2})$ ~且 ~$\Delta(H_{1})\geq \frac{n+7}{2}$,~则~$\mu
(H_{1})> \mu (H_{2}).$ 作为该结论的应用,~确定了~${\mathcal
T}(n)(n\geq9)$~中图的第七大至第十九大的拉普拉斯谱半径及其相应的极图.     

4p阶三度点传递图

一个图称为点传递图或对称图如果它的自同构群分别在点集或点集有序对上传递.设P为素数,给出了4p阶连通三度点传递图分类(徐明曜等在[Chin.Ann.Math.,2004,25B(4):545-554]中分类了4p阶连通三度对称图).确定了4p阶互不同构的连通三度点传递图的个数f(4p);当P=2,3,5,7时,f(4p)分别为2,4,8,6;当P≥11且4|(p-1)时,f(4p)=5+p-3/2,当P≥11且4|(p-1)时,f(4p)=3+p-3/2.     

循环图的Adam同构的性质

本文得到了任意两个连通循环图是(?)d(?)m同构的充要条件,并且还得到两个连通循环图是(?)d(?)m同构的另一必要条件。     

随机图的广义3-连通度

图的广义连通度的概念是由Chartrand等人引入的.令S表示图G的一个非空顶点集,κ(S)表示图G中连结S的内部不交树的最大数目.那么,对任意一个满足2≤r≤n的整数r,定义G的广义r-连通度为所有κ(S)中的最小值,其中S取遍G的顶点集合的r-元子集.显然,κ_2(G)=κ(G),即为图G的顶点连通度.所以广义连通度是经典连通度的一个自然推广.本文研究了随机图的广义3-连通度,证明了对任一给定的整数k,k≥1,p=(log n+(k+1)log long n-log lon logn)/n是关于性质κ_3(G(n,p))≥k的紧阈值函数.我们得到的结果可以看作是Bollobas和Thomason给出的关于经典连通度结果的推广.     

给定最大度的单圈偶图的谱半径

单圈偶图是边数等于顶点数的简单连通偶图.Δ（G）表示图G的最大度.文中给出了最大度为Δ(≥ⁿ⁺¹/2)的n阶单圈偶图的谱半径的上界,并刻画了达到该上界的图.文中还证明了当Δ（G）≥[（2n+1）/3]+1时,n（≥8）阶单圈偶图G的谱半径随着最大度的递增而严格递增,并在此基础上给出了谱半径排在前17位的n（≥16）阶单圈偶图.     

邻域并与泛圈图

本文中 ,我们用邻域并对泛圈图进行深入的研究 ,主要取得了“2连通 n( n≥ 3 )阶图 G,满足下列条件之一 ,则 G是泛圈图 : :δ≤ ( n-7) /3 ,N C≥ ( 2 n-3 ) /3 ; :( n-6) /3≤ δ≤ ( n+2 ) /3 ,N C≥ 2 n/3 ; :δ≥ ( n+3 ) /3 ,N C≥ ( 2 n-3 ) /3 .当 3≤ n≤ 14时 ,N C≥ 2 n/3”     

连通的K_{n}-残差图

m-K_{n}-残差图是由P. Erd\"{o}s, F. Harary和M. Klawe等人提出的, 当m=1时, 他们证明了当n\neq1,2,3,4时, K_{n+1}\timesK_{2}是唯一的具有最小阶的连通的K_{n}- 残差图. 首先得到了m-K_{n}-残差图的重要性质, 同时证明了当n=1,2,3,4时, 连通K_{n}-残差图的最小阶和极图, 其中当n=1,2时得到唯一极图; 当n=3,4时, 证明了恰有两个不同构的极图, 从而彻底解决连通的K_{n}-残差图的最小阶和极图问题. 最后证明了当n\neq1,2,3,4时, K_{n+1}\timesK_{2}是唯一的具有最小阶的连通的K_{n}-残差图.     

给定顶点数和边数的连通图的Q-谱半径的界

图的无符号拉普拉斯矩阵是图的邻接矩阵和度对角矩阵的和,其特征值记为q1≥q2≥…≥qn.设C(n,m)是由n个顶点m条边的连通图构成的集合,这里1≤n-1≤m≤(n2).如果对于任意的G∈C(n,m)都有q1(G*)≥q1(G)成立,图G*∈C(n,m)叫做最大图.这篇文章证明了对任意给定的正整数a=m-n+1,如果n...