Groupe d’études et de recherche en analyse des décisions

G-2005-09

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

et

Le système AutoGraphiX (AGX1 et AGX2) permet, parmi d’autres fonctions, la génération automatique de conjectures en théorie des graphes. Nous étudions ici des conjectures obtenues par ce système et de la forme $\underline{b}_n \leq g \oplus i \leq \overline{b}_n$ 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, $\underline{b}_n$ et $\overline{b}_n$ des fonctions de l’ordre n = |V| de g les meilleures possibles, enfin $\oplus$ correspond à une des opérations +,−,×, /.

48 telles conjectures sont obtenues : les plus simples sont démontrées automatique- ment et les autres à la main. De plus 12 autres conjectures ouvertes et non encore étudiées sont soumises aux lecteurs.

, 22 pages

Ce cahier a été révisé en novembre 2005