Completely Independent Spanning Trees on Some Interconnection Networks
Summary :
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 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.
- Publication
- IEICE TRANSACTIONS on Information Vol.E97-D No.9 pp.2514-2517
- Publication Date
- 2014/09/01
- Publicized
- Online ISSN
- 1745-1361
- DOI
- 10.1587/transinf.2014EDL8079
- Type of Manuscript
- LETTER
- Category
- Information Network
Authors
Kung-Jui PAI
Ming Chi University of Technology
Jinn-Shyong YANG
National Taipei University of Business
Sing-Chen YAO
National Taipei University of Business
Shyue-Ming TANG
National Defense University
Jou-Ming CHANG
National Taipei University of Business
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Kung-Jui PAI, Jinn-Shyong YANG, Sing-Chen YAO, Shyue-Ming TANG, Jou-Ming CHANG, "Completely Independent Spanning Trees on Some Interconnection Networks" in IEICE TRANSACTIONS on Information,
vol. E97-D, no. 9, pp. 2514-2517, September 2014, doi: 10.1587/transinf.2014EDL8079.
Abstract: 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 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.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2014EDL8079/_p
Copy
@ARTICLE{e97-d_9_2514,
author={Kung-Jui PAI, Jinn-Shyong YANG, Sing-Chen YAO, Shyue-Ming TANG, Jou-Ming CHANG, },
journal={IEICE TRANSACTIONS on Information},
title={Completely Independent Spanning Trees on Some Interconnection Networks},
year={2014},
volume={E97-D},
number={9},
pages={2514-2517},
abstract={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 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.},
keywords={},
doi={10.1587/transinf.2014EDL8079},
ISSN={1745-1361},
month={September},}
Copy
TY - JOUR
TI - Completely Independent Spanning Trees on Some Interconnection Networks
T2 - IEICE TRANSACTIONS on Information
SP - 2514
EP - 2517
AU - Kung-Jui PAI
AU - Jinn-Shyong YANG
AU - Sing-Chen YAO
AU - Shyue-Ming TANG
AU - Jou-Ming CHANG
PY - 2014
DO - 10.1587/transinf.2014EDL8079
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E97-D
IS - 9
JA - IEICE TRANSACTIONS on Information
Y1 - September 2014
AB - 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 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.
ER -
English
