孤立韧度变量和分数(k,n)-临界图

孤立韧度变量I′(G)是衡量网络健壮性的有效工具,定义|S|和i(G-S)-1的最小比值,其中S■V(G)满足i(G-S)>1。图G称为分数(k,n)-临界图,若从G中删除任意n个顶点,其剩余子图依然存在分数k-因子。文献[10]中得到分数k-因子存在性的紧I′(G)界。论文将文献[10]的结果推广到分数临界图,即:若δ(G)≥k+n且I′(G)>2k+n-1,则G是分数(k,n)-临界图,其中k≥2和n≥0是整数。

完全图K_(n)的{P_(5),C_(5)}分解

图分解问题已在很多邻域中得到了广泛的应用。用P_(5)表示5个顶点的路,C_(5)表示5个顶点的圈,本研究讨论了完全图Kn分解成5个顶点的路P5和圈C_(5)的存在性,给出完全图Kn存在{P5,C_(5)}-强制分解的充分必要条件是n≥7(n≠8),以及完全图Kn存在{P5,C_(5)}-分解的充分必要条件是n≥5(n≠6)。

Hamiltonian[k,k+1]-因子(英文)

本文考虑n/2-临界图中Hamiltonian[k,k+1]-因子的存在性。Hamiltonian[k,k+1]-因子是指包含Hamiltonian圈的[k,k+1]-因子;给定阶数为n的简单图G,若δ(G)≥n/2而δ(G\e)<n/2(对任意的e∈E(G)),则称G为n/2-临界图。设k为大于等于2的整数,G为n/2-临界图(其中n≥4k-6且n≥7),我们证明了对于G的任何Hamiltonian圈C,G中必存在包含C的[k,k+1]-因子。该结果改进了现有的一些有关Hamiltonian[k,k+1]-因子存在性的结果。

k×n格图P_k×P_n的控制数

k× n格图 Pk× Pn是长为 k- 1的路与长为 n- 1的路的积 .我们证明了对充分大的 k和 n,Pk × Pn 的控制数不超过 [(k + 2 ) (n + 2 ) / 5 ]- 4.

(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.

路与完全图的笛卡尔积图和广义图K(n,m)的关联色数

RichardA .Brualdi和J .QuinnMassey在 [1]中引入了图的关联着色概念 ,并且提出了关联着色猜想 ,即 :每一个图G都可以用Δ(G) +2种色正常关联着色 .B .Guiduli[2 ]说明关联着色的概念是I.Algor和N .Alon[3]提出的有向星荫度的一个特殊情况 ,并证实 [1]的关联着色猜想是错的 ,给出图G的关联色数的一个新的上界是Δ(G) +O(Log(ΔG) ) .[4 ]确定了某些特殊图类的关联色数 .本文给出了路和完全图的笛卡尔积图的关联色数 ,而且利用此结果又确定了完全图Kn 的广义图K(n ,m)

广义图K(n,m)的点强全色数

图G(V,E)的一个正常k-全染色σ称为G(V,E)的一个k-点强全染色,当且仅当v∈V(G),N[v]中的元素着不同颜色,其中N[v]={u vu∈V(G)}∪{v};并且χvTs(G)=m in{k存在G的一个k-点强全染色}称为G的点强全色数.本文确定了完全图Kn的广义图K(n,m)和乘积图Lm×Kn的点强全色数.

广义图K(n,m)的全色数(英文)

196 5年 ,M.Behzad和 Vizing分别提出了著名的全着色猜想 :即对于简单图 G有 :XT( G)≤Δ + 2 ,其中Δ是图 G的最大度 .本文确定了完全图 Kn的广义图 K( n,m)的全色数 ,并利用它证明了 Lm× Kn( m≥ 3)是第 I型的 .

连通、N_2-局部连通、K_(1,4)-受限图的哈密顿性

证明如下结论 :设G是连通、N2 -局部连通、δ≥ 6的K1 ,4 -受限图 ,如果G中不含有同构于G1 ,G2 或G3的导出子图H ,则G含哈密顿圈 .

完全图K_n和完全多部图K_n(t)的｛C_3,S_4｝-强制分解

本文给出完全图Kn 和完全多部图Kn(t)存在｛C3 ,S4｝

具有(n,k)-正交的(g,f)-因子分解的子图

设G是一个图,g和f是定义在V(G)上的两个整数函数且对每个x∈V(G)有g≤f。本文证明了如下结果:设k是一个正整数,G是一个(mg+nk,mf-nk) 图,其中1≤n<m,H是G的任意一个有nk条边的子图。若对每个x∈V(G)有g≥k,则G中存在子图R,R具有(g,f) 因子分解与H(n,k) 正交。

K(n,m)图的边色数

设K(n,0)=Kn,V(Kn)={v_1～0,v_2～0…,v_n～0},分别从v_1～0,v_2～0,…,v_(n-1)～0,出发作长为m的n-1条路v_i～0,v_i～1,…,v_i～m,i=1,2,…,n-1;然后,对j=1,2,…,m,添加边{v_i～jv_k～j|k,i=1,2,…,n-1,且k≠i},这样得到的图用K(n,m)表示.证明了对图K(n,m)当n≥2、m≥1时的边色数为n.

关于图P_n^k和图B(3,2,k),B(4,3,k)的强协调性

证明了图Pkn和B(3,2,k),B(4,3,k)都是强协调图,并给出了它们的强协调标号.进一步讨论了图Pkn(k 3)的强协调性.

Fubini定理公式数计数和齘(n,k)卷积公式

组合数学中,Catalan数有显式公式,Fubini定理公式数无显式公式,本文利用完全图Kn 的k 个分支的完全分支覆盖的个数N(Kn,k)=S(n,k)(第二类Stirling数)和卷积公式,作者将导出Fubini定理的公式数的显式公式,此外获得完全i 部图所有个数基数公式,本文中提出(n,k)概念,并讨论(n,k)的组合卷积公式,最后证明(n)=∑nk=1(n,k)与Fubini公式数之间的关系等式.

图K_n-E(K_r),K_r“非汉字字符”K_n的和数σ与整和数ζ的关系

针对 1 994年F .Harary提出的关于和图与整和图的未决问题 ,对Kn-E(Kr) ,Kr Kn,详细讨论了ζ(Kn-E(Kr) )与σ(Kn-E(Kr) )的关系 ,并对任意的n ,r,n≥r≥ 1 ,给出了其完整的结果。

完全图K_n中边不重的3圈数

设完全图Kn 中边不重的 3圈数的最大值为c(n ,3) ,证明了 { (n - 1) (n - 2 )6 }≤c(n ,3)≤ [n[n - 12 ]3 ],当n≡ 1,2 ,3(mod 6 )时 ,c(n ,3) =[n[n - 12 ]3 ],并给出了一个得到Kn 中 { (n - 1) (n - 2 )6 }个边不重的 3圈的方法 ,其中n∈ { 3,4,5 ,… } .

Fubini定理公式数计数和φ(n,k)卷积公式

组合数学中,Catalan数有显式公式,Fibini定理公式数无显式公式,本文利用完全图Kn的k个分支的完全分支覆盖的个数N(Knk)=S(n,k)(第二类Stirling数)和卷积公式,作者将导出Fibini定理的公式数的显式公式,此外获得完全i-部图所有个数计数公式,本文中提出φ(n,k)概念,并讨论φ(n,k)的组合卷积公式,最后证明φ(n)=sumfork=1ton(1/k)φ(n,k)与Fibini公式数之间的关系等式。

完全二部图的超k-Steiner Wiener指数

文章利用Hosoya多项式和组合恒等式给出了完全二部图Km,n的超k-Steiner Wiener指数的计算公式.

关于完全图K_(n)的{P_4,C_4}-分解

讨论了完全图K_(n)分解成四个顶点的路和圈的存在性,给出完全图K_(n)存在{P_(4),C_(4)}-强制分解的充要条件是n≥5且n≠6.以及完全图K_(n)存在{P_(4),C_(4)}-分解的充要条件是n≥4.

(n,k)-星图网络的t/m-诊断度及诊断算法

故障诊断度在衡量多处理机系统可靠性上起着极其重要的作用.t/m-诊断分析是一种能极大提高多处理机系统自我诊断性能的诊断策略,该诊断策略能至多识别t个故障处理机,其中最多包含m个被误诊的无故障处理机.在PMC诊断模型下,证明了(n,k)-星图是n+(m-1)k-2m+1/m-可诊断的,其中2≤m≤4,且给出了复杂度为O(NlogN)的快速诊断算法来识别所有的故障节点,其中N是(n,k)-星图网络节点总数.