Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4949789 | Discrete Applied Mathematics | 2017 | 12 Pages |
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.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Benoit Darties, Nicolas Gastineau, Olivier Togni,