基于顶点度数的完全独立生成树研究

• 作者: 林政宽 樊建席 程宝雷 赵源
• 来源期刊: 计算机科学
• 学科: 工学
• 关键词: 完全独立生成树 可靠传输 互连网络 图
• 年，卷（期）: 2017,（6）
• 所属期刊栏目: 网络与通信
• 页码范围: 94-96,107
• 页数: 4页
• 分类号: TP393
• 字数: 6186字
• 语种: 中文
• DOI: 10.11896/j.issn.1002-137X.2017.06.016

摘要

在计算机互连网络中,完全独立生成树在信息的可靠传输、并行传输、安全分发等方面具有重要的作用.假设图G中存在n棵生成树T1,T2,,Tn,若对于图G中任意两个顶点u和v,满足u和v之间的路径在这n棵树中都是顶点不相交的,则称这n棵树为完全独立生成树(CISTs).在2015年,Chang等人证明了对于包含n(n≥6)个顶点的任意图G,如果图G的最小顶点度数至少为n-2,那么,G中存在至少[n/3]棵CISTs[1].在Chang等人的基础上,文中继续深入研究了图G中顶点度数和CISTs的棵数之间的关系.对于包含n(n≥5)个顶点的任意图G,假设图G的最小顶点度数至少为n-2,得出度数为n-2的顶点的个数、度数为n-1的顶点的个数与图G中CISTs的棵数之间关系的推导等式,并证明了其正确性,从而改进了文献[1]中的结果.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	樊建席	苏州大学计算机科学与技术学院	22	147	7.0	11.0
2	林政宽	苏州大学计算机科学与技术学院	9	16	2.0	3.0
3	程宝雷	苏州大学计算机科学与技术学院	10	57	5.0	7.0
5	赵源	苏州大学计算机科学与技术学院	12	9	1.0	3.0