Article ID Journal Published Year Pages File Type
4949789 Discrete Applied Mathematics 2017 12 Pages PDF
Abstract
Let k≥2 be an integer and T1,…,Tk be spanning trees of a graph G. If for any pair of vertices {u,v} of V(G), the paths between u and v in every Ti, 1≤i≤k, do not contain common edges and common vertices, except the vertices u and v, then T1,…,Tk are completely independent spanning trees in G. For 2k-regular graphs which are 2k-connected, such as the Cartesian product of a complete graph of order 2k−1 and a cycle, and some Cartesian products of three cycles (for k=3), the maximum number of completely independent spanning trees contained in these graphs is determined and it turns out that this maximum is not always k.
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, , ,