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

研究成果: 雜誌貢獻 › 期刊論文 › 同行評審

28 引文斯高帕斯（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.

原文	英語
頁（從 - 到）	2191-2193
頁數	3
期刊	IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences
卷	E98A
發行號	10
DOIs	https://doi.org/10.1587/transfun.E98.A.2191
出版狀態	已發佈 - 2015 10月 1
對外發佈	是

ASJC Scopus subject areas

訊號處理
電腦繪圖與電腦輔助設計
電氣與電子工程
應用數學

存取文件

10.1587/transfun.E98.A.2191

其它文件與鏈接

引用此

@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

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

SN - 0916-8508

IS - 10

ER -

A note on the degree condition of completely independent spanning trees

摘要

ASJC Scopus subject areas

存取文件

其它文件與鏈接

指紋

引用此