Completely Independent Spanning Trees on Some Interconnection Networks
スポンサーリンク
概要
- 論文の詳細を見る
Let T1,T2,...,Tk 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 T1,T2,...,Tk 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 Péterfalvi recently. In this note, we give a necessary condition for k-connected k-regular graphs with ⌊k/2⌋ CISTs. Based on this condition, we provide more counterexamples for Hasunumas 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.
- The Institute of Electronics, Information and Communication Engineersの論文
The Institute of Electronics, Information and Communication Engineers | 論文
- Compensation Effect of Quasi-Inverse Filter (QIF) on Frequency Characteristic Distortion in Wideband Systems
- Subblock Processing for Frequency-Domain Turbo Equalization under Fast Fading Environments
- Measurement-Based Performance Evaluation of Coded MIMO-OFDM Spatial Multiplexing with MMSE Spatial Filtering in an Indoor Line-of-Sight Environment
- Design of a Multiple-Input SC DC-DC Converter Realizing Long Battery Runtime
- The Influence of a Low-Level Color or Figure Adaptation on a High-Level Face Perception