A note on the degree condition of completely independent spanning trees

Hung Yi Chang, Hung Lung Wang, Jinn Shyong Yang, Jou Ming Chang

Research output: Contribution to journalArticlepeer-review

33 Citations (Scopus)


Given a graph G, a set of spanning trees of G are completely independent 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. In this paper, we prove that for graphs of order n, with n ≤ 6, if the minimum degree is at least n-2, then there are at least [n/3] completely independent spanning trees.

Original languageEnglish
Pages (from-to)2191-2193
Number of pages3
JournalIEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences
Issue number10
Publication statusPublished - 2015 Oct 1
Externally publishedYes


  • Completely independent trees
  • Dirac's condition
  • Ore's condition

ASJC Scopus subject areas

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


Dive into the research topics of 'A note on the degree condition of completely independent spanning trees'. Together they form a unique fingerprint.

Cite this