2014/09/21 by Benoit Darties, Darties, Benoit, Nicolas Gastineau +3
Computer Science · Mathematics · #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #cs.DM #math.CO
paper · pdf · doi:10.48550/arxiv.1409.6002
arxiv created 2014/09/21 · arxiv updated 2014/09/23
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 from u to v in each 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.