Almost disjoint spanning treesReport as inadecuate

Almost disjoint spanning trees - Download this document for free, or read online. Document in PDF available to download.

1 Le2i - Laboratoire Electronique, Informatique et Image

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 IT 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.

Author: Benoit Darties - Nicolas Gastineau - Olivier Togni -



Related documents