A note on the degree condition of completely independent spanning trees

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

doi:10.1587/transfun.E98.A.2191

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 journal › Article › peer-review

33 Citations (Scopus)

Abstract

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 language	English
Pages (from-to)	2191-2193
Number of pages	3
Journal	IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences
Volume	E98A
Issue number	10
DOIs	https://doi.org/10.1587/transfun.E98.A.2191
Publication status	Published - 2015 Oct 1
Externally published	Yes

Keywords

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

Access to Document

10.1587/transfun.E98.A.2191

Cite this

@article{14cae429f4f145e3afa86e7172aed990,

title = "A note on the degree condition of completely independent spanning trees",

abstract = "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.",

keywords = "Completely independent trees, Dirac's condition, Ore's condition",

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

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

year = "2015",

month = oct,

day = "1",

doi = "10.1587/transfun.E98.A.2191",

language = "English",

volume = "E98A",

pages = "2191--2193",

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

issn = "0916-8508",

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

number = "10",

}

TY - JOUR

T1 - A note on the degree condition of completely independent spanning trees

AU - Chang, Hung Yi

AU - Wang, Hung Lung

AU - Yang, Jinn Shyong

AU - Chang, Jou Ming

PY - 2015/10/1

Y1 - 2015/10/1

N2 - 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.

AB - 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.

KW - Completely independent trees

KW - Dirac's condition

KW - Ore's condition

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

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

U2 - 10.1587/transfun.E98.A.2191

DO - 10.1587/transfun.E98.A.2191

M3 - Article

AN - SCOPUS:84942942599

SN - 0916-8508

VL - E98A

SP - 2191

EP - 2193

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

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

IS - 10

ER -

A note on the degree condition of completely independent spanning trees

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this