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 journalArticlepeer-review

10 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 languageEnglish
Pages (from-to)1932-1935
Number of pages4
JournalIEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences
VolumeE100A
Issue number9
DOIs
Publication statusPublished - 2017 Sep
Externally publishedYes

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

Fingerprint

Dive into the research topics of 'Completely independent spanning trees on 4-regular chordal rings'. Together they form a unique fingerprint.

Cite this