期刊文献+

全有向图的幂敛指数(英文)

The Index of Convergence of the Total Digraph
下载PDF
导出
摘要 设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为有向圈C_n时,k(T(D))=2n-1.2.对任意非平凡强连通图D,k(T(D))≥Diam(D)+1.我们还证明了以上界是不可改进的最好界. Let D be a digraph, T(D) denote the total digraph of D, k(D) and p(D) denote the index of convergence and the period of D, respectively. Following results are obtained in this paper: 1. For a non-trivial digraph D, then p(T(D)) = 1, and k(T(D)) ≤ max{2p(D) -1,2k(D) + 1}. Especially, we prove that k(T(D)) ≤ k(D) + 1 if D is a primitive digraph; and k(T(D)) = 2k(D) - 1 if there are not directed cycles in D; and k(T(D)) = 2_n - 1 if D is a directed cycle C_n. 2. For a strongly connected digraph D, then k(T(D)) ≥ Diam(D) + 1, where Diam(D) denotes the diameter of D. We also proved that these bounds are best.
出处 《运筹学学报》 CSCD 北大核心 2002年第4期57-64,共8页 Operations Research Transactions
基金 ThisworkissupportedbyNSFC(19971071)andFJECF(JA97138).
关键词 线有向图 全有向图 幂敛指数 周期 邻接矩阵 Line digraph, Total digraph, Index of convergence, Period, Adjacency matrix.
  • 相关文献

参考文献1

二级参考文献5

共引文献3

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部