Almost disjoint spanning trees: Relaxing the conditions for completely independent spanning trees
Link to item filehttps://hal.archives-ouvertes.fr/hal-01715892
DeweyPrincipes généraux des mathématiques
SujetCompletely independent spanning trees; Disjoint connected dominating sets; Independent spanning trees; Grid; Spanning trees
Journal issueDiscrete Applied Mathematics
MetadataShow full item record
Abstract (EN)The search of spanning trees with interesting disjunction properties has led to the introduction of edge-disjoint spanning trees, independent spanning trees and more recently completely independent spanning trees. We group together these notions by defining (i,j)-disjoint spanning trees, where i (j respectively) is the number of vertices (edges, respectively) that are shared by more than one tree. We illustrate how (i,j)-disjoint spanning trees provide some nuances between the existence of disjoint connected dominating sets and completely independent spanning trees. We prove that determining if there exist two (i,j)-disjoint spanning trees in a graph is NP-complete, for every two positive integers i and j. Moreover we prove that for square of graphs, k-connected interval graphs, complete graphs and several grids, there exist(i,j) -disjoint spanning trees for interesting values of i and j.
Showing items related by title, author, creator and subject.
Branzei, Rodica; Gök, Zeynep Alparslan; Moretti, Stefano; Tijs, Stef (2011) Article accepté pour publication ou publié
Gourvès, Laurent; Escoffier, Bruno; Spanjaard, Olivier; Monnot, Jérôme (2010) Article accepté pour publication ou publié
Alfandari, Laurent; Paschos, Vangelis (1999) Article accepté pour publication ou publié