Recherche à voisinage variable de graphes extrémaux 13. à propos de la mailleVariable neighborhood search for extremal graphs 13. on girth

Issue		RAIRO Oper. Res. Volume 39, Number 4, October-December 2005


Page(s)		275 - 293
DOI		10.1051/ro:2006006
Published online		08 April 2006

RAIRO Oper. Res. 39 (2005) 275-293
DOI: 10.1051/ro:2006006

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

Mustapha Aouchiche¹ and Pierre Hansen²

¹ 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 le 20 janvier 2005. Accepté le 9 décembre 2005 / Publié en ligne le 8 avril 2006)

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 $\underline{b}_{n} \, \le \, g \, \oplus \, i \, \le \, \overline{b}_{n}$ 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, $\underline{b}_{n}$ and $\overline{b}_{n}$ best possible functions of the order n of G, and $\oplus$ denotes one of the four operations $+, -, \times, /$ . 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.

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 $\underline{b}_{n} \, \le \, g \, \oplus \, i \, \le \, \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 $+, -, \times, /$ . 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.

What is OpenURL?

The OpenURL standard is a protocol for transmission of metadata describing the resource that you wish to access. An OpenURL link contains article metadata and directs it to the OpenURL server of your choice. The OpenURL server can provide access to the resource and also offer complementary services (specific search engine, export of references...). The OpenURL link can be generated by different means.

If your librarian has set up your subscription with an OpenURL resolver, OpenURL links appear automatically on the abstract pages.
You can define your own OpenURL resolver with your EDPS Account. In this case your choice will be given priority over that of your library.
You can use an add-on for your browser (Firefox or I.E.) to display OpenURL links on a page (see http://www.openly.com/openurlref/). You should disable this module if you wish to use the OpenURL server that you or your library have defined.