Logo image
Se connecter
Recherche d'arbres couvrants complètement indépendants dans des graphes réguliers
Acte de colloque

Recherche d'arbres couvrants complètement indépendants dans des graphes réguliers

Nicolas Gastineau, Benoit Darties et Olivier Togni
pp.1-4
ALGOTEL 2014 -- 16èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications
2014

Résumé

Computational Complexity Computer Science
Nous étudions l'existence de $r$ arbres couvrants complètement indépendants dans des graphes $2r$-réguliers et $2r$-connexes, et énonçons des conditions nécessaires à leur existence. Nous déterminons le nombre maximum d'arbres dans les produits cartésiens d'une clique et d'un cycle. Nous montrons que ce nombre n'est pas toujours $r$.

Indicateurs

1 Consultations de la notice

Détails

Logo image