全有向图的幂敛指数

摘要：

设D为有向图,T(D)为D的全有向图(Total-digraph),k(D)与p(D)分别为D的幂敛指数(Index of convergence)与周期(Period).本文证明了,1.对任意非平凡有向图D,p(T(D))=1,k(T(D))≤max{2p(D)-1,2k(D)+1),特别地,当D为本原有向图时,k(T(D))≤k(D)+1;当D不含有向圈时,k(T(D))=2k(D)-1;当D为有向圈Cn时,k(T(D))=2n-1.2.对任意非平凡强连通图D,k(T(D))≥Diam(D)+1.我们还证明了以上界是不可改进的最好界.

关键词：线有向图、全有向图、幂敛指数、周期、邻接矩阵

所属期刊栏目：6

分类号：O22(运筹学)

资助基金：国家自然科学基金19971071;FJECFJA97138

在线出版日期：2004-08-18（万方平台首次上网日期，不代表论文的发表时间）

页数：共8页

页码：57-64