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

Translated title of the contribution: Variable neighborhood search for extremal graphs. 13. About the network

Mustapha Aouchiche, Pierre Hansen

Research output: Contribution to journalArticlepeer-review

7 Citations (Scopus)


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 bn ≤ g ⊕ ≤ 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, bn and b̄ best possible functions of the order n of G, and ⊕ denotes one of the four operations +, -, x, /. 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.

Translated title of the contributionVariable neighborhood search for extremal graphs. 13. About the network
Original languageFrench
Pages (from-to)275-293
Number of pages19
JournalRAIRO - Operations Research
Issue number4
Publication statusPublished - 2005
Externally publishedYes

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science Applications
  • Management Science and Operations Research


Dive into the research topics of 'Variable neighborhood search for extremal graphs. 13. About the network'. Together they form a unique fingerprint.

Cite this