6533b7d6fe1ef96bd12666a8
RESEARCH PRODUCT
Almost disjoint spanning trees: relaxing the conditions for completely independent spanning trees
Benoit DartiesOlivier TogniNicolas Gastineausubject
FOS: Computer and information sciences[INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC]Discrete Mathematics (cs.DM)Spanning trees[ INFO.INFO-NI ] Computer Science [cs]/Networking and Internet Architecture [cs.NI]0102 computer and information sciences02 engineering and technologyMinimum spanning tree[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]01 natural sciencesConnected dominating setCombinatorics[INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI]0202 electrical engineering electronic engineering information engineeringDiscrete Mathematics and CombinatoricsGridMathematicsMinimum degree spanning treeDiscrete mathematics020203 distributed computingTrémaux treeSpanning treeApplied MathematicsShortest-path treeWeight-balanced tree[ INFO.INFO-DM ] Computer Science [cs]/Discrete Mathematics [cs.DM]Disjoint connected dominating setsIndependent spanning trees[ INFO.INFO-CC ] Computer Science [cs]/Computational Complexity [cs.CC]010201 computation theory & mathematicsReverse-delete algorithmCompletely independent spanning treesComputer Science - Discrete MathematicsMathematicsofComputing_DISCRETEMATHEMATICSdescription
International audience; 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 dening (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 G 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.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2017-02-24 |