Completely Independent Spanning Trees on 4-Regular Chordal Rings

Jou-Ming CHANG; Hung-Yi CHANG; Hung-Lung WANG; Kung-Jui PAI; Jinn-Shyong YANG

doi:10.1587/transfun.E100.A.1932

Completely Independent Spanning Trees on 4-Regular Chordal Rings

Jou-Ming CHANG, Hung-Yi CHANG, Hung-Lung WANG, Kung-Jui PAI, Jinn-Shyong YANG

Full Text Views

0

Share
Cite this

Summary :

Given a graph G, a set of spanning trees of G are completely independent spanning trees (CISTs for short) if for any vertices x and y, the paths connecting them on these trees have neither vertex nor edge in common, except x and y. Hasunuma (2001, 2002) first introduced the concept of CISTs and conjectured that there are k CISTs in any 2k-connected graph. Later on, this conjecture was unfortunately disproved by Péterfalvi (2012). In this note, we show that Hasunuma's conjecture holds for graphs restricted in the class of 4-regular chordal rings CR(n,d), where both n and d are even integers.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E100-A No.9 pp.1932-1935

Publication Date: 2017/09/01

Publicized

Online ISSN: 1745-1337

DOI: 10.1587/transfun.E100.A.1932

Type of Manuscript: Special Section LETTER (Special Section on Discrete Mathematics and Its Applications)

Category

Authors

Jou-Ming CHANG
  National Taipei University of Business
Hung-Yi CHANG
  National Taipei University of Business
Hung-Lung WANG
  National Taipei University of Business
Kung-Jui PAI
  Ming Chi University of Technology
Jinn-Shyong YANG
  National Taipei University of Business

Keyword

completely independent spanning trees, chordal rings, distributed loop networks

Cite this

Copy

Jou-Ming CHANG, Hung-Yi CHANG, Hung-Lung WANG, Kung-Jui PAI, Jinn-Shyong YANG, "Completely Independent Spanning Trees on 4-Regular Chordal Rings" in IEICE TRANSACTIONS on Fundamentals, vol. E100-A, no. 9, pp. 1932-1935, September 2017, doi: 10.1587/transfun.E100.A.1932.
Abstract: Given a graph G, a set of spanning trees of G are completely independent spanning trees (CISTs for short) if for any vertices x and y, the paths connecting them on these trees have neither vertex nor edge in common, except x and y. Hasunuma (2001, 2002) first introduced the concept of CISTs and conjectured that there are k CISTs in any 2k-connected graph. Later on, this conjecture was unfortunately disproved by Péterfalvi (2012). In this note, we show that Hasunuma's conjecture holds for graphs restricted in the class of 4-regular chordal rings CR(n,d), where both n and d are even integers.
URL: https://globals.ieice.org/en_transactions/fundamentals/10.1587/transfun.E100.A.1932/_p

Copy

@ARTICLE{e100-a_9_1932,
author={Jou-Ming CHANG, Hung-Yi CHANG, Hung-Lung WANG, Kung-Jui PAI, Jinn-Shyong YANG, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Completely Independent Spanning Trees on 4-Regular Chordal Rings},
year={2017},
volume={E100-A},
number={9},
pages={1932-1935},
abstract={Given a graph G, a set of spanning trees of G are completely independent spanning trees (CISTs for short) if for any vertices x and y, the paths connecting them on these trees have neither vertex nor edge in common, except x and y. Hasunuma (2001, 2002) first introduced the concept of CISTs and conjectured that there are k CISTs in any 2k-connected graph. Later on, this conjecture was unfortunately disproved by Péterfalvi (2012). In this note, we show that Hasunuma's conjecture holds for graphs restricted in the class of 4-regular chordal rings CR(n,d), where both n and d are even integers.},
keywords={},
doi={10.1587/transfun.E100.A.1932},
ISSN={1745-1337},
month={September},}

Copy

TY - JOUR
TI - Completely Independent Spanning Trees on 4-Regular Chordal Rings
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1932
EP - 1935
AU - Jou-Ming CHANG
AU - Hung-Yi CHANG
AU - Hung-Lung WANG
AU - Kung-Jui PAI
AU - Jinn-Shyong YANG
PY - 2017
DO - 10.1587/transfun.E100.A.1932
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E100-A
IS - 9
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - September 2017
AB - Given a graph G, a set of spanning trees of G are completely independent spanning trees (CISTs for short) if for any vertices x and y, the paths connecting them on these trees have neither vertex nor edge in common, except x and y. Hasunuma (2001, 2002) first introduced the concept of CISTs and conjectured that there are k CISTs in any 2k-connected graph. Later on, this conjecture was unfortunately disproved by Péterfalvi (2012). In this note, we show that Hasunuma's conjecture holds for graphs restricted in the class of 4-regular chordal rings CR(n,d), where both n and d are even integers.
ER -