Arbres couvrants presque disjoints

2015

International audience; Dans un réseau, la recherche de plusieurs arbres couvrants avec des propriétés intéressantes a amené à l'introduc-tion de plusieurs notions : les arbres couvrants arête-disjoints, les arbres indépendants enracinés en un sommet et les arbres complètement indépendants. Afin de généraliser ces notions, nous introduisons la notion d'arbres couvrants (i, j)-disjoints, où i et j sont respectivement le nombre maximum de noeuds internes et d'arêtes communs aux arbres couvrants. Nous montrons que déterminer s'il existe deux arbres couvrants (i, j)-disjoints dans un graphe G est un problème NP-complet pour i et j quelconques, et nous déterminons les valeurs minimales de i et j…