Recherche à voisinage variable de graphes extrémaux 13. à propos de la maille^*

Variable neighborhood search for extremal graphs 13. on girth

¹ Département de mathématiques et génie industriel, École Polytechnique de Montréal, Qc, Canada; Mustapha.Aouchiche@gerad.ca
² GERAD et Service de l'enseignement des méthodes quantitatives de gestion HEC Montréal, Qc, Canada; Pierre.Hansen@gerad.ca

Reçu : 20 Janvier 2005
Accepté : 9 Décembre 2005

Résumé

Le système AutoGraphiX (AGX1 et AGX2) permet, parmi d'autres fonctions, la génération automatique de conjectures en théorie des graphes et, dans une version plus récente, la preuve automatique de conjectures simples. Afin d'illustrer ces fonctions et le type de résultats obtenus, nous étudions systématiquement ici des conjectures obtenues par ce système et de la forme où g désigne la maille (ou longueur du plus petit cycle) du graphe G=(V, E), i un autre invariant choisi parmi le nombre de stabilité, le rayon, le diamètre, le degré minimum, moyen ou maximum, et des fonctions de l'ordre n = |V| de G les meilleures possibles, enfin correspond à une des opérations +,-,×,/. 48 telles conjectures sont obtenues: les plus simples sont démontrées automatiquement et les autres à la main. De plus 12 autres conjectures ouvertes et non encore étudiées sont soumises aux lecteurs.

Abstract

The AutoGraphiX system (AGX1 et AGX2) allows, among other functions, automated generation of conjectures in graph theory and, in its most recent version, automated proof of simple conjectures. To illustrate these functions and the type of results obtained, we study systematically in this paper, conjectures of the form where g denotes the girth (or length of the smallest cycle) of a graph G=(V, E), i another invariant among independence number, radius,iameter, minimum, average or maximum degree, and best possible functions of the order n of G, and denotes one of the four operations +,-,×,/. 48 such conjectures are obtained: the easiest ones are proved automatically and the others by hand. Moreover 12 open and unstudied conjectures are submitted to the readers.