期刊
THEORETICAL COMPUTER SCIENCE
卷 465, 期 -, 页码 61-72出版社
ELSEVIER SCIENCE BV
DOI: 10.1016/j.tcs.2012.08.020
关键词
Independent spanning tree; Fault-tolerant broadcasting; Secure message distribution; Parity cube
资金
- National Natural Science Foundation of China [61170021, 61173137, 61202028, 60970117]
- Specialized Research Fund for the Doctoral Program of Higher Education [20103201110018]
- Natural Science Foundation of the Jiangsu Higher Education Institutions of China [12KJB520016]
- Application Foundation Research of Suzhou of China [SYG201240]
- Qing Lan Project
Independent spanning trees have applications in networks such as reliable communication protocols, one-to-all broadcasting, reliable broadcasting, and secure message distribution. Thus, the designs of independent spanning trees in several classes of networks have been widely investigated. However, there is a conjecture on independent spanning trees: any n-connected graph has n independent spanning trees rooted at an arbitrary vertex. This conjecture still remains open for n >= 5. In this paper, by proposing an algorithm to construct n independent spanning trees rooted at any vertex, we confirm the conjecture on n-dimensional parity cube PQ(n) - a variant of n-dimensional hypercube. Furthermore, we prove that all independent spanning trees rooted at an arbitrary vertex constructed by our construction method are isomorphic and the height of each tree is n + 1 for any integer it >= 2. (c) 2012 Elsevier B.V. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据