Completely Independent Spanning Trees in Some Regular Graphs

الأصل · EN

Let k≥ 2 be an integer and T₁,, Tₖ 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 Tᵢ, 1≤ i≤ k, do not contain common edges and common vertices, except the vertices u and v, then T₁,, Tₖ 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.