Almost disjoint spanning trees

Abstract : In this extended abstract, we only consider connected graphs. Let k ≥ 2 be an integer and T 1 ,. .. , T k be spanning trees in a graph G. A vertex is said to be an inner vertex in a tree T if it has degree at least 2 in T. We denote by I(T) the set of inner vertices of tree T. The spanning trees T 1 ,. .. , T k are completely independent spanning trees if any vertex from G is an inner vertex in at most one tree among T 1 ,. .. , T k and the trees T 1 ,. .. , T k are pairwise edge-disjoint. Completely independent spanning trees were introduced by Hasunuma [4] and then have been studied on different classes of graphs, such as underlying graphs of line graphs [4], maximal planar graphs [5], Cartesian product of two cycles [6] and k-trees [10]. Moreover, determining if there exist two completely independent spanning trees in a graph G is a NP-hard problem [5]. Recently, sufficient conditions inspired by the sufficient conditions for hamiltonicity have been determined in order to guarantee the existence of several completely independent spanning trees: Dirac's condition [1] and Ore's condition [2]. Moreover, Dirac's condition has been generalized to more than two trees [7].
Type de document :
Communication dans un congrès
Bordeaux Graph Workshop BGW, Nov 2016, Bordeaux, France. 〈http://bgw.labri.fr/2016/〉
Liste complète des métadonnées

Littérature citée [11 références]  Voir  Masquer  Télécharger

https://hal-univ-bourgogne.archives-ouvertes.fr/hal-01451683
Contributeur : Benoît Darties <>
Soumis le : mercredi 1 février 2017 - 12:36:47
Dernière modification le : mardi 7 février 2017 - 01:02:10

Fichier

BGW2016_almost_disjoint_trees....
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01451683, version 1

Collections

Citation

Benoit Darties, Nicolas Gastineau, Olivier Togni. Almost disjoint spanning trees. Bordeaux Graph Workshop BGW, Nov 2016, Bordeaux, France. 〈http://bgw.labri.fr/2016/〉. 〈hal-01451683〉

Partager

Métriques

Consultations de la notice

81

Téléchargements de fichiers

42