Indexed by:
Abstract:
Let T-1, T-2,...,T-k be spanning trees of a graph G. For any two vertices u, v of G, if the paths from u to v in these k trees are pairwise openly disjoint, then we say that T-1, T-2,...,T-k are completely independent. Araki showed that a graph G on n >= 7 vertices has two completely independent spanning trees if the minimum degree delta(G) >= n/2. In this paper, we give a generalization: a graph G on n >= 4k - 1 vertices has k completely independent spanning trees if the minimum degree delta(G) >= k-1/kn. In fact, we prove a stronger result. (C) 2016 Elsevier B.V. All rights reserved.
Keyword:
Reprint 's Address:
Email:
Version:
Source :
INFORMATION PROCESSING LETTERS
ISSN: 0020-0190
Year: 2016
Issue: 10
Volume: 116
Page: 644-648
0 . 7 4 8
JCR@2016
0 . 7 0 0
JCR@2023
ESI Discipline: COMPUTER SCIENCE;
ESI HC Threshold:175
JCR Journal Grade:4
CAS Journal Grade:4
Cited Count:
WoS CC Cited Count: 29
SCOPUS Cited Count: 33
ESI Highly Cited Papers on the List: 0 Unfold All
WanFang Cited Count:
Chinese Cited Count:
30 Days PV: 1
Affiliated Colleges: