期刊
IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS
卷 E97D, 期 9, 页码 2514-2517出版社
IEICE-INST ELECTRONICS INFORMATION COMMUNICATIONS ENG
DOI: 10.1587/transinf.2014EDL8079
关键词
completely independent spanning trees; interconnection networks; chordal rings
资金
- Ministry of Science and Techonology of Taiwan [NSC101-2221-E-131-039, NSC102-2221-E-141-0002, NSC102-2221-E-141-001-MY3]
Let T-1, T-2, ... , T-k be spanning trees in a graph G. If, for any two vertices u, v of G, the paths joining u and v on the k trees are mutually vertex-disjoint, then T-1, T-2, ... , T-k are called completely independent spanning trees (CISTs for short) of G. The construction of CISTs can be applied in fault-tolerant broadcasting and secure message distribution on interconnection networks. Hasunuma (2001) first introduced the concept of CISTs and conjectured that there are k CISTs in any 2k-connected graph. Unfortunately, this conjecture was disproved by Peterfalvi recently. In this note, we give a necessary condition for k-connected k-regular graphs with left perpendiculark/2right perpendicular CISTs. Based on this condition, we provide more counterexamples for Hasunuma's conjecture. By contrast, we show that there are two CISTs in 4-regular chordal rings CR(N, d) with N = k(d - 1) + j under the condition that k >= 4 is even and 0 <= j <= 4. In particular, the diameter of each constructed CIST is derived.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据