Existence d'un cycle de longueur au moins 7 dans un graphe sans (1,=<2)-jumeaux
Rapport interne Telecom ParisTech-2009D015, Paris, France, 18 pages, juillet 2009.
David AUGER, Irène CHARON, Olivier HUDRY & Antoine LOBSTEIN
Centre National de la Recherche Scientifique
Ecole Nationale Supérieure des Télécommunications
46 rue Barrault, 75634 Paris cédex 13, France
{auger, charon, hudry, lobstein}@enst.fr
Résumé. On considère un graphe G simple non orienté, ayant au moins deux sommets. On appelle boule d'un sous-ensemble Y de sommets de G l'ensemble des sommets de G à distance au plus 1 d'un sommet de Y. On suppose que les boules des sous-ensembles des sommets de G de cardinal au plus 2 sont toutes distinctes. On montre que, si G est connexe, alors G possède un cycle de longueur au moins 7 ; sinon, les composantes connexes de G sont réduites à un sommet ou contiennent chacune un cycle de longueur au moins 7.