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

Issue		RAIRO Oper. Res. Volume 43, Number 4, October-December 2009


Page(s)		339 - 358
DOI		10.1051/ro/2009022
Published online		08 October 2009

RAIRO-Oper. Res. 43 (2009) 339-358
DOI: 10.1051/ro/2009022

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

Mustapha Aouchiche¹, Odile Favaron^{2, 3} et Pierre Hansen⁴

¹ 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 le 4 juin, 2008. Accepté le 7 mars, 2009. Publié en ligne le 8 octobre 2009

Abstract
Using the AutoGraphiX 2 system (AGX2), we study relations between graph invariants of the form

$\begin{displaymath}\underline{b}_{n} \, \le \, g \, \oplus \, i \, \le \, \overline{b}_{n} \end{displaymath}$

where g denotes the girth of a graph G=(V, E), i another invariant among the average distance $\overline{l}$ , the index $\lambda_1$ , the Randić index R and the domination number $\beta$ , $\oplus$ denotes one of the four operations $+, -, \times, /$ , $\underline{b}_{n}$ and $\overline{b}_{n}$ 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].

Résumé
On étudie à l'aide du système AutoGraphiX 2 (AGX 2) des relations de la forme

$\begin{displaymath}\underline{b}_{n} \, \le \, g \, \oplus \, i \, \le \, \overline{b}_{n} \end{displaymath}$

où g désigne la maille d'un graphe G=(V, E), i un autre invariant parmi la distance moyenne $\overline{l}$ , l'index $\lambda_1$ , l'indice de Randić R et le nombre de domination $\beta$ , $\oplus$ désigne l'une des opérations $+, -, \times, /$ , $\underline{b}_{n}$ et $\overline{b}_{n}$ des fonctions de l'ordre n du graphe qui bornent l'expression $g\oplus i$ 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].

Mathematics Subject Classification. 05C35, 05C12.

Key words: Graph, AGX, girth, distance, Randić, index, domination.

Mots clés : Graphe, AGX, maille, distance, Randić, index, domination.

© EDP Sciences, ROADEF, SMAI 2009

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.