Completely independent spanning trees in some regular graphs - Archive ouverte HAL Accéder directement au contenu
Article Dans Une Revue Discrete Applied Mathematics Année : 2017

Completely independent spanning trees in some regular graphs

(1) , (1, 2) , (1)
1
2

Résumé

Let k >= 2 be an integer and T-1,..., T-k 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 T-i, 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. (C) 2016 Elsevier B.V. All rights reserved.

Dates et versions

hal-01469367 , version 1 (16-02-2017)

Identifiants

Citer

Benoit Darties, Nicolas Gastineau, Olivier Togni. Completely independent spanning trees in some regular graphs. Discrete Applied Mathematics, 2017, 217, pp.163 - 174. ⟨10.1016/j.dam.2016.09.007⟩. ⟨hal-01469367⟩
309 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook Twitter LinkedIn More