Completely independent spanning trees in some regular graphs

Benoit Darties 1, * Nicolas Gastineau 2, 1, * Olivier Togni 1, *
* Auteur correspondant
2 GrAMA - Graphes, Algorithmes et Multi-Agents
LIRIS - Laboratoire d'InfoRmatique en Image et Systèmes d'information
Abstract : 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.
Type de document :
Article dans une revue
Liste complète des métadonnées
Contributeur : Le2i - Université de Bourgogne <>
Soumis le : jeudi 16 février 2017 - 13:26:36
Dernière modification le : jeudi 8 février 2018 - 11:10:20



Benoit Darties, Nicolas Gastineau, Olivier Togni. Completely independent spanning trees in some regular graphs. Discrete Applied Mathematics, Elsevier, 2017, 217, pp.163 - 174. 〈〉. 〈10.1016/j.dam.2016.09.007〉. 〈hal-01469367〉



Consultations de la notice