Paper Info
Title
Minimum Degree Conditions and Optimal Graphs for Completely Independent Spanning Trees.
Abstract
Completely independent spanning trees (T_1,T_2,ldots ,T_k) in a graph G are spanning trees in G such that for any pair of distinct vertices u and v, the k paths in the spanning trees between u and v mutually have no common edge and no common vertex except for u and v. The concept finds applications in fault-tolerant communication problems in a network. Recently, it was shown that Dirac’s condition for a graph to be hamiltonian is also a sufficient condition for a graph to have two completely independent spanning trees. In this paper, we generalize this result to three or more completely independent spanning trees. Namely, we show that for any graph G with (n ge 7) vertices, if the minimum degree of a vertex in G is at least (n-k), where (3 le k le frac{n}{2}), then there are (lfloor frac{n}{k} rfloor ) completely independent spanning trees in G. Besides, we improve the lower bound of (frac{n}{2}) on the Dirac’s condition for completely independent spanning trees to (frac{n-1}{2}) except for some specific graph. Our results are theoretical ones, since these minimum degree conditions can be applied only to a very dense graph. We then present constructions of symmetric regular graphs which include optimal graphs with respect to the number of completely independent spanning trees.
Year
Venue
Field
2015
IWOCA
Combinatorics,Minimum degree spanning tree,Vertex (geometry),Upper and lower bounds,Degree (graph theory),Spanning tree,Mathematics,Maximal independent set,Minimum spanning tree,Dense graph
DocType
Citations 
PageRank 
Conference
7
0.54
References 
Authors
9
1
Name
Order
Citations
PageRank
Toru Hasunuma114216.00