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
Discrete Applied Mathematics, Elsevier, 2017, 217, pp.163 - 174. <http://www.sciencedirect.com/science/article/pii/S0166218X16303997>. <10.1016/j.dam.2016.09.007>
Liste complète des métadonnées

https://hal-univ-bourgogne.archives-ouvertes.fr/hal-01469367
Contributeur : Le2i - Université de Bourgogne <>
Soumis le : jeudi 16 février 2017 - 13:26:36
Dernière modification le : vendredi 10 mars 2017 - 15:09:06

Identifiants

Collections

Citation

Benoit Darties, Nicolas Gastineau, Olivier Togni. Completely independent spanning trees in some regular graphs. Discrete Applied Mathematics, Elsevier, 2017, 217, pp.163 - 174. <http://www.sciencedirect.com/science/article/pii/S0166218X16303997>. <10.1016/j.dam.2016.09.007>. <hal-01469367>

Partager

Métriques

Consultations de la notice

198