首页 | 本学科首页   官方微博 | 高级检索  
     检索      

全有向图的幂敛指数
引用本文:晏卫根,张福基.全有向图的幂敛指数[J].运筹学学报,2002,6(4):57-64.
作者姓名:晏卫根  张福基
作者单位:1. 集美大学师范学院数学系,厦门361021
2. 厦门大学数学系,厦门,361005
基金项目:ThisworkissupportedbyNSFC(19971071)andFJECF(JA97138).
摘    要:设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。我们还证明了以上界是不可改进的最好界。

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

The Index of Convergence of the Total Digraph
WEIGEN YAN FUJI ZHANG.The Index of Convergence of the Total Digraph[J].OR Transactions,2002,6(4):57-64.
Authors:WEIGEN YAN FUJI ZHANG
Abstract:Let D be a digraph, T(D) denote the total digraph of D, k(D) and p(D) de-note the index of convergence and the period of D, respectively. Following resultsare obtained in this paper: 1. For a non-trivial digraph D, then p(T(D)) = 1, andk(T(D)) ≤ max{2p(D) - 1, 2k(D) + 1). Especially, we prove that k(T(D)) ≤ k(D) + 1 ifD is a primitive digraph; and k(T(D)) = 2k(D) - 1 if there are not directed cycles in D;and k(T(D)) = 2n - 1 if D is a directed cycle Cn. 2. For a strongly connected digraphD, then k(T(D)) ≥ Diam(D) + 1, where Diam(D) denotes the diameter of D. We alsoproved that these bounds are best.
Keywords:Line digraph  Total digraph  Index of convergence  Period  Adjacency matrix  
本文献已被 CNKI 维普 万方数据 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号