Recherche à voisinage variable de graphes extrémaux 26. Nouveaux résultats sur la maille

¹ HEC Montréal, Qc, Canada; Mustapha.Aouchiche@gerad.ca
² Univ Paris-Sud, LRI, UMR 8623, Orsay, 91405, France.
³ CNRS, Orsay, 91405, France; of@LRI.lri.fr
⁴ GERAD et HEC Montréal, Qc, Canada; Pierre.Hansen@gerad.ca

Reçu : 4 Juin 2008
Accepté : 7 Mars 2009

Résumé

On étudie à l'aide du système AutoGraphiX 2 (AGX 2) des relations de la forme où g désigne la maille d'un graphe G=(V, E), i un autre invariant parmi la distance moyenne , l'index λ₁, l'indice de Randić R et le nombre de domination β, désigne l'une des opérations +, -, ×, /, et des fonctions de l'ordre n du graphe qui bornent l'expression et sont atteintes pour tout n (sauf éventuellement de très petites valeurs du fait des effets de bord). Les résultats prouvés ou discutés ci-dessous ont déjà été présentés, sous forme de conjectures, dans un article précédent paru dans RAIRO Recherche Opérationnelle [RAIRO Oper. Res. 39 (2005) 275–293].

Abstract

Using the AutoGraphiX 2 system (AGX2), we study relations between graph invariants of the form where g denotes the girth of a graph G=(V, E), i another invariant among the average distance , the index λ₁, the Randić index R and the domination number β, denotes one of the four operations +, -, ×, /, and lower and upper bounding functions of the order n of the graph considered which are tight for all n (except possibly very small values due to border effects). The results proved or discussed below were first presented as conjectures in a previous paper published in RAIRO Operations Research [RAIRO Oper. Res. 39 (2005) 275–293].