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.
Hung-Yi CHANG
National Taipei University of Business
Hung-Lung WANG
National Taipei University of Business
Jinn-Shyong YANG
National Taipei University of Business
Jou-Ming CHANG
National Taipei University of Business
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copy
Hung-Yi CHANG, Hung-Lung WANG, Jinn-Shyong YANG, Jou-Ming CHANG, "A Note on the Degree Condition of Completely Independent Spanning Trees" in IEICE TRANSACTIONS on Fundamentals,
vol. E98-A, no. 10, pp. 2191-2193, October 2015, doi: 10.1587/transfun.E98.A.2191.
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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E98.A.2191/_p
Copy
@ARTICLE{e98-a_10_2191,
author={Hung-Yi CHANG, Hung-Lung WANG, Jinn-Shyong YANG, Jou-Ming CHANG, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={A Note on the Degree Condition of Completely Independent Spanning Trees},
year={2015},
volume={E98-A},
number={10},
pages={2191-2193},
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={},
doi={10.1587/transfun.E98.A.2191},
ISSN={1745-1337},
month={October},}
Copy
TY - JOUR
TI - A Note on the Degree Condition of Completely Independent Spanning Trees
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 2191
EP - 2193
AU - Hung-Yi CHANG
AU - Hung-Lung WANG
AU - Jinn-Shyong YANG
AU - Jou-Ming CHANG
PY - 2015
DO - 10.1587/transfun.E98.A.2191
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E98-A
IS - 10
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - October 2015
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.
ER -