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

Aouchiche, Mustapha ; Favaron, Odile  ; Hansen, Pierre 

RAIRO - Operations Research - Recherche Opérationnelle, Tome 43 (2009) no. 4, pp. 339-358

Abstract (VO)

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

$${\underline{b}}_n\le g\oplus i\le {\overline{b}}_n$$

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

$${\underline{b}}_n\le g\oplus i\le {\overline{b}}_n$$

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].

Détail

DOI : 10.1051/ro/2009022

Classification : 05C35, 05C12
Keywords: graph, AGX, girth, distance, Randić, index, domination
Mots-clés : graphe, AGX, maille, distance, Randić, index, domination