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

^*Corresponding author for this work

Research output: Contribution to journal › Article › peer-review

14 Citations (Scopus)

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 2kconnected graph. Later on, this conjecture was unfortunately disproved by Peterfalvi (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.

Original language	English
Pages (from-to)	1932-1935
Number of pages	4
Journal	IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences
Volume	E100A
Issue number	9
DOIs	https://doi.org/10.1587/transfun.E100.A.1932
Publication status	Published - 2017 Sept
Externally published	Yes

Keywords

Chordal rings
Completely independent spanning trees
Distributed loop networks

ASJC Scopus subject areas

Signal Processing
Computer Graphics and Computer-Aided Design
Electrical and Electronic Engineering
Applied Mathematics

Access to Document

10.1587/transfun.E100.A.1932

Cite this

@article{eb9dd4daf36646ef960c89140b2b36fc,

title = "Completely independent spanning trees on 4-regular chordal rings",

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 2kconnected graph. Later on, this conjecture was unfortunately disproved by Peterfalvi (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 = "Chordal rings, Completely independent spanning trees, Distributed loop networks",

author = "Chang, {Jou Ming} and Chang, {Hung Yi} and Wang, {Hung Lung} and Pai, {Kung Jui} and Yang, {Jinn Shyong}",

note = "Publisher Copyright: Copyright {\textcopyright} 2017 The Institute of Electronics, Information and Communication Engineers.",

year = "2017",

month = sep,

doi = "10.1587/transfun.E100.A.1932",

language = "English",

volume = "E100A",

pages = "1932--1935",

journal = "IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences",

issn = "0916-8508",

publisher = "Maruzen Co., Ltd/Maruzen Kabushikikaisha",

number = "9",

}

TY - JOUR

T1 - Completely independent spanning trees on 4-regular chordal rings

AU - Chang, Jou Ming

AU - Chang, Hung Yi

AU - Wang, Hung Lung

AU - Pai, Kung Jui

AU - Yang, Jinn Shyong

PY - 2017/9

Y1 - 2017/9

N2 - 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 2kconnected graph. Later on, this conjecture was unfortunately disproved by Peterfalvi (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.

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 2kconnected graph. Later on, this conjecture was unfortunately disproved by Peterfalvi (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.

KW - Chordal rings

KW - Completely independent spanning trees

KW - Distributed loop networks

UR - http://www.scopus.com/inward/record.url?scp=85028768901&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85028768901&partnerID=8YFLogxK

U2 - 10.1587/transfun.E100.A.1932

DO - 10.1587/transfun.E100.A.1932

M3 - Article

AN - SCOPUS:85028768901

SN - 0916-8508

VL - E100A

SP - 1932

EP - 1935

JO - IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences

JF - IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences

IS - 9

ER -

Completely independent spanning trees on 4-regular chordal rings

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this