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

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

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

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

[1] M. Aouchiche, Comparaison automatisée d'invariants en théorie des graphes. Ph.D. Thesis, École Polytechnique de Montréal, February (2006). Disponible sur www.gerad.ca/~agx.

[2] M. Aouchiche, G. Caporossi and P. Hansen, Variable neighborhood search for extremal graphs. 20. Automated comparison of graph invariants. MATCH Commun. Math. Comput. Chem. 58 (2007) 365-384. | MR

[3] M. Aouchiche, J.-M. Bonnefoy, A. Fidahoussen, G. Caporossi, P. Hansen, L. Hiesse, J. Lacheré and A. Monhait, Variable Neighborhood Search for Extremal Graphs. 14. The AutoGraphiX 2 System, in Global Optimization: From theory to implementation, edited by L. Liberti and N. Maculan, Springer (2006) 281-310. | Zbl | MR

[4] M. Aouchiche and P. Hansen, Recherche à voisinage variable de graphes extrémaux. XIII. À propos de la maille. (French) RAIRO-Oper. Res. 39 (2005) 275-293. | Zbl | MR | Numdam

[5] M. Aouchiche, P. Hansen and M. Zheng, Variable neighborhood search for extremal graphs. 19. Further conjectures and results about the Randić index. MATCH Commun. Math. Comput. Chem. 58 (2007) 83-102. | Zbl | MR

[6] B. Bollobás and P. Erdös, Graphs of extremal weights. Ars Combin. 50 (1998) 225-233. | Zbl | MR

[7] J.A. Bondy and F.Y. Halberstam, Parity theorems for paths and cycles in graphs. J. Graph Theory 10 (1986) 107-115. | Zbl | MR

[8] G. Caporossi and P. Hansen, Variable neighborhood search for extremal graphs. I. The AutGraphiX system. Disc. Math. 212 (2000) 29-44. | Zbl | MR

[9] D. Cvetković, M. Doob and H. Sachs, Spectra of graphs - Theory and application. Academic Press, New York (1982). | MR

[10] D. Cvetković and P. Rowlinson, Spectra of unicyclic graphs. Graphs and combinatorics 3 (1987) 7-23. | Zbl | MR

[11] C. Delorme, O. Favaron and D. Rautenbach, On the Randić index. Discrete Math. 257 (2002) 29-38. | Zbl | MR

[12] F.M. Dong and K.M. Koh, The Sizes of Graph with Small Girth. Bull. Inst. Combin. Appl. 18 (1996) 33-44. | Zbl | MR

[13] R.D. Dutton and R.C. Brigham, Edges in Graphs with Large Girth. Graphs Combin. 7 (1991) 315-321. | Zbl | MR

[14] A.J. Hoffman, On Limit Points of Spectral Radii of Non-Negative Symmetric Integral Matrices, in Graph Theory and Applications. Lect. Notes Math. 303, edited by Y. Alavi, D.R. Lick, A.T. White, Springer-Verlag, Berlin (1972) 165-172. | Zbl | MR

[15] Q. Li, and K.Q. Feng, On the largest eigenvalue of a graph. Acta Math. Appl. Sinica 2 (1979) 167-175. | MR

[16] G. Liu, Y. Zhu and J. Cai, On the Randić index of unicyclic graphs with girth $g$. MATCH Commun. Math. Comput. Chem. 58 (2007) 127-138. | Zbl | MR

[17] P. Turán, An extremal problem in graph theory. Mat. Fiz. Lapok 48 (1941) 436-452. | Zbl